2024 February 17 Problems

55 views
Skip to first unread message

daryl...@gmail.com

unread,
Feb 17, 2024, 12:43:25 PMFeb 17
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.


2810Faulty Keyboard82.7%Easy


Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

Flocela Maldonado

unread,
Feb 17, 2024, 1:28:00 PMFeb 17
to leetcode-meetup
2810Faulty Keyboard82.7%Easy class Solution {
public:
string finalString(string s) {
stringstream stream{};
// i's indices
vector<int> indices{};
for (int idx=0; idx<s.size(); ++idx)
{
if (s[idx] != 'i')
{
stream << s[idx];
}
else
{
indices.push_back(idx);
}
}

string str = stream.str();

// number of skipped i's so far
int count = 0;
for (int index : indices)
{
reverse(str.begin(), str.begin() + index - count);
++count;
}

return str;

}
};

Flocela Maldonado

unread,
Feb 17, 2024, 1:46:04 PMFeb 17
to leetcode-meetup
2785Sort Vowels in a String81.9%Medium
Time: O(n + nlg(n)) Space: O(n). Where n is the length of the string str.
class Solution {
public:
string sortVowels(string s) {
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

vector<char> chars{};
vector<int> charIndices{};
for (int ii=0; ii<s.size(); ++ii)
{
char c = s[ii];
if (vowels.find(c) != vowels.end())
{
chars.push_back(c);
charIndices.push_back(ii);
}
}
sort(chars.begin(), chars.end());

for (int ii=0; ii<chars.size(); ++ii)
{
s[charIndices[ii]] = chars[ii];
}

return s;
}
};

Carlos Green

unread,
Feb 17, 2024, 2:04:49 PMFeb 17
to leetcode-meetup
/**

Time O(n * m) where n = length of s and m = the about if 'i' characters
Space O(n)

Iterate over the string and whenever we hit 'i'
reverse the previous concatenation of the string
then return the final result

**/

/**
* @param {string} s
* @return {string}
*/
var finalString = function(s) {
let result = ''

for (let i = 0; i < s.length; i++) {
if (s[i] === 'i') {
result = result.split('').reverse().join('')
} else {
result += s[i]
}
}

return result
};

Carlos Green

unread,
Feb 17, 2024, 2:16:36 PMFeb 17
to leetcode-meetup
/**

Time O(n log m) where n is our s string and m is our ASCII characters
Space O(n)

Change our s string into an array

Create a set to keep track of all the ASCII vowels
Create a sorted array to keep track of the current
values inside of the s string

Iterate over the s string and if the current index
is a vowel then add it to our sorted array
then replace the current character with '*'

then sort our sorted array based on their ASCII values
iterate over our s array and when we hit our '*' character
just add the next sorted ASCII value
**/

/**
* @param {string} s
* @return {string}
*/
var sortVowels = function(s) {
s = s.split('')
const vowels = new Set("aeiouAEIOU".split(''))
const sorted = []

for (let i = 0; i < s.length; i++) {
if (vowels.has(s[i])) {
sorted.push(s[i])
s[i] = '*'
}
}

sorted.sort().reverse()

for (let i = 0; i < s.length; i++) {
if (s[i] === '*') {
s[i] = sorted.pop()
}
}

return s.join('')
};

Flocela Maldonado

unread,
Feb 24, 2024, 11:03:31 PMFeb 24
to leetcode-meetup
2746Decremental String Concatenation25.8%Medium
Time: O(2^n), where n is words.length. Memory n.
class Solution {
public:

int rec(int index, string firstAndLast, vector<string>& words, unordered_map<string,int>& negativesPerIndexAndFirstAndLast)
{
string keyString = to_string(index);
// first and last is just the first and last letters of the word.
keyString.append(firstAndLast);

if (index == words.size()-1)
{
return 0;
}
if (negativesPerIndexAndFirstAndLast.find(keyString) != negativesPerIndexAndFirstAndLast.end())
{
return negativesPerIndexAndFirstAndLast[keyString];
}
else
{
int firstAndLastSize = firstAndLast.size();
// wordAtIndexPlusOne will be prepended or appended to firstAndLast.
string wordAtIndexPlusOne = words[index+1];
int wordAtIndexPlusOneSize = wordAtIndexPlusOne.size();

// Case 0: Prepend wordAtIndexPlusOne
// When I join firstLast with wordAtIndexPlusOne, I may increase the number of negatives (negatives are the number of letter deletions).
// negativesPerPrepend is the number of deletions that happen if I prepend wordAtIndexPlusOne.
// deletions happen when the last letter from the first word matches the first letter from the second word.
int negativesPerPrepend = (firstAndLast[0] == wordAtIndexPlusOne[wordAtIndexPlusOneSize-1]) ? 1 : 0;

// Join firstAndLast with wordAtIndexPlusOne, but just keep the first and last letters.
string newWord = "";
newWord.append(1, wordAtIndexPlusOne[0]);
newWord.append(1, firstAndLast[firstAndLastSize-1]);

int resultFromPrepend = rec(index+1, newWord, words, negativesPerIndexAndFirstAndLast) + negativesPerPrepend;

// Case 1: Append wordAtIndexPlusOne Case
newWord = "";
// negativesPerAppend is the number of deletions if I append wordAtIndexPlusOne.
int negativesPerAppend = (firstAndLast[firstAndLastSize-1] == wordAtIndexPlusOne[0]) ? 1 : 0;
newWord.append(1, firstAndLast[0]);
newWord.append(1, wordAtIndexPlusOne[wordAtIndexPlusOneSize-1]);

int resultAppend = rec(index+1, newWord, words, negativesPerIndexAndFirstAndLast) + negativesPerAppend;

int maxNegatives = max(resultFromPrepend, resultAppend);

negativesPerIndexAndFirstAndLast.insert({keyString, maxNegatives});

return negativesPerIndexAndFirstAndLast[keyString];
}
}

int minimizeConcatenatedLength(vector<string>& words) {
// Sum of all the word lengths in words
int sum = 0;
for (const string& word : words)
{
sum += word.size();
}

// The number of deletions per "index and first and last letters".
// So at index 0, the first word is "abc", the "index plus first and last letters" is "0ac"
unordered_map<string,int> negativesPerIndexAndFirstAndLast{};

// Don't need the whole first word. Shorten word to just the first and last letters of the word.
string firstWord;
firstWord.append(1, words[0][0]);
if (words[0].size() > 1)
{
firstWord.append(1, words[0][words[0].size()-1]);
}

// Trying all the cases, this is the max number of deletions. I'm calling them negatives.
int bestNegatives = rec(0, firstWord, words, negativesPerIndexAndFirstAndLast);

// Subtract the number of deleted letters from the sum.
return sum - bestNegatives;
}
};

Jagrut

unread,
Feb 24, 2024, 11:35:26 PMFeb 24
to leetcode-meetup
2810 Faulty Keyboard

class Solution {
public:
    string finalString(string s) {
        std::deque<char> str;
        bool reverseFlag = false;
        for (auto c: s) {
            if (c == 'i') {
                reverseFlag = !reverseFlag;
            }
            else {
                reverseFlag ? str.push_front(c) : str.push_back(c);
            }
        }
        return (reverseFlag) ? std::string(str.rbegin(), str.rend()) :  std::string(str.begin(), str.end());
    }
};
On Saturday, February 17, 2024 at 9:43:25 AM UTC-8 daryl...@gmail.com wrote:
Reply all
Reply to author
Forward
0 new messages