2024 June 22 Problems

[daryl...@gmail.com]

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.

942DI String Match78.8%Easy

28Find the Index of the First Occurrence in a String42.7%Easy

1717Maximum Score From Removing Substrings47.1%Medium

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 (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

[Flocela Maldonado]

942DI String Match78.8%Easy
Time: O(n), Memory O(n)

class Solution {

public:

vector<int> diStringMatch(string s) {

int dCount = 0;

for(char c : s)

{

if (c == 'D')

{

++dCount;

}

}

vector<int> ans{};

int top = dCount;

int bot = dCount - 1;

ans.push_back(top);

++top;

for(char c : s)

{

if (c == 'D')

{

ans.push_back(bot);

--bot;

}

else

{

ans.push_back(top);

++top;

}

}

return ans;

}

};

[Carlos Green]

/**

* @param {string} haystack

* @param {string} needle

* @return {number}

* Time O(n) & Space O(1)

**/

var strStr = function(haystack, needle) {

for (let i = 0; i < haystack.length; i++) {

if (haystack[i] === needle[0]) {

const clone = haystack.slice(i, i + needle.length)

if (clone === needle) return i

}

}

return -1

};

/**

var strStr = function(haystack, needle) {

if (haystack.includes(needle)) {

return haystack.indexOf(needle)

}

return -1

};

**/

[Arjun Malhotra]

func diStringMatch(s string) []int {

res := make([]int,len(s)+1)

f := 0

l := len(s)

for i:=0;i<len(s);i++ {

if s[i] == 'I' {

res[i] = f

f++

} else {

res[i] = l

l--

}

}

res[len(s)] = f

return res

}

[Silvi Monga]

DI String match:

class Solution:

def diStringMatch(self, s: str) -> List[int]:

res = [-1] * (len(s)+1)

count = 0

for i in range(len(s)):

if s[i] == 'I':

res[i] = count

count += 1

revCount = len(s)

for j in range(len(res)):

if res[j] == -1 and revCount > count-1:

res[j] = revCount

revCount -= 1

return res

28. Find the Index of the First Occurrence in a String

class Solution:

def strStr(self, haystack: str, needle: str) -> int:

i = 0

while i < len(haystack):

if haystack[i : i+len(needle)] == needle:

return i

else:

i += 1

return -1

[Priyank Gupta]

# Time : O(n)

# Space: O(1)

# we just have to see the local values, when encounter "I" then take the min values and when "D" take the max values.

class Solution:

def diStringMatch(self, s: str) -> List[int]:

mi,ma = 0, len(s)

res = []

for c in s:

if c == "I":

res.append(mi)

mi += 1

else:

res.append(ma)

ma -= 1

return res.append(mi)

# Time : O((n-m)*m) => n = len(haystack), m = len(needle)

# Space: O(1)

# Two pointer, for each char in haystack expand the 2nd pointer until you find the match with needle, if not successe then shrink the 2nd pointer and try the same approach with next char in haystack.

class Solution:

def strStr(self, haystack: str, needle: str) -> int:

n, m = len(haystack), len(needle)

for i in range(n-m+1):

s = 0

while(s <= m-1 and needle[s] == haystack[i+s]):

s += 1

if s == m:

return i

return -1

# Time : O(n + n) = O(n)

# Space: O(n + n) = O(n)

class Solution:

def maximumGain(self, s: str, x: int, y: int) -> int:

if x > y:

s, score1 = self.removeAB(s, x)

s, score2 = self.removeBA(s, y)

return score1 + score2

else:

s, score1 = self.removeBA(s, y)

s, score2 = self.removeAB(s, x)

return score1 + score2

def removeAB(self, s, x):

stack, count = [], 0

for i in range(len(s)):

if stack == []:

stack.append(s[i])

elif s[i] == "b" and stack[-1] == "a":

stack.pop()

count += 1

else:

stack.append(s[i])

return stack, count*x

def removeBA(self, s, x):

stack, count = [], 0

for i in range(len(s)):

if stack == []:

stack.append(s[i])

elif s[i] == "a" and stack[-1] == "b":

stack.pop()

count += 1

else:

stack.append(s[i])

return stack, count*x

[Anne-Elise Chung]

1717 Max score from removing substrings

/**

* @param {string} s

* @param {number} x

* @param {number} y

* @return {number}

*/

var maximumGain = function (s, x, y) {

let a = 'a';

let b = 'b';

if (x < y) {

[x, y] = [y, x];

[a, b] = [b, a];

}

let score = 0;

let a_count = 0;

let b_count = 0;

for (let c of s) {

if (c === a) {

++a_count;

} else if (c === b) {

if (a_count > 0) {

--a_count;

score += x;

} else {

++b_count;

}

} else {

score += Math.min(a_count, b_count) * y;

a_count = 0;

b_count = 0;

}

}

score += Math.min(a_count, b_count) * y;

return score;

};

Approach: 

At first I tried to use brute force with string.include() and string.replace() but I got stopped by TLE (time limit exceeded) when submitting the solution.

In my next attempt, I tried to look at other's solutions to help me understand how to find a more optimal solution. I ended up adopting a C++ solution from GoogleNick.
The JavaScript solution I ended up with will iterate through each character in the string.

First, we decide whether or not to prioritize searching for "ab" or "ba" depending on if x is greater than or less than y. If y is greater than x, then we switch the x and y assignments as well as the b and assignments to set up for the next block of code.

If we are greedily searching for "ab" then it will increment the count for 'a' when 'a' appears, and decrement the count for 'a' if 'b' appears. Every time b appears after a, it means we have encountered "ab" in the string, so we increase the score by x. If we encounter a character that does not match 'a' or 'b', then we reset the counts because that means that we are entering a new subsection of the string that will not be able to accrue more "ab" occurrences. Upon resetting, we can account for any remaining "ba" occurrences by getting the smaller of the two count values and multiplying by y.

Time Complexity: O(n) because we will need to iterate through all n characters in the given string.

Space Complexity: O(1)

On Saturday, June 22, 2024 at 9:28:20 AM UTC-7 daryl...@gmail.com wrote:

[Flocela Maldonado]

1717Maximum Score From Removing Substrings47.1%Medium

Time: O(n). Memory: O(1)

class Solution {

public:

int maximumGain(string s, int x, int y) {

int n = s.size();

int points = 0;

// A pair is made up of a major and minor letter. The first letter is the major and the second letter is the minor.

// If y > x, then the pairs to reap first are "ba", because "ba" will be worth more than "ab".

char major= (y > x) ? 'b' : 'a';

char minor = (y > x) ? 'a' : 'b';

int large = (y > x) ? y : x;

int small = (y > x) ? x : y;

// majorCount is the number of times the major letter has been seen so far. Decrease this value

// every time the minor letter is found. This means a major pair, (major, minor), has been found

// and one of the major letters was used up, so decrease majorCount.

// If a minor letter is encountered when majorCount is zero, then increase the minorCount.

// Use up these minor pairs at the end. If at the end of this iteration, there is a minorCount

// and a majorCount, then those are the minor pairs. They are the cases where a minor letter was found

// before a major letter was found.

int majorCount = 0;

int minorCount = 0;

for(int ii=0; ii<n; ++ii)

{

// If the character is not an 'a' or 'b', then start all the counts over at zero.

// Pairs can't be made across these non 'a''b' barriers.

// Do increase the count by the number of minor pairs.

if (s[ii] != major && s[ii] != minor)

{

points += (std::min(majorCount, minorCount)) * small;

majorCount = 0;

minorCount = 0;

continue;

}

if(s[ii] == major)

{

++majorCount;

}

else if (majorCount > 0)

{

points += large;

--majorCount;

}

else

{

++minorCount;

}

}

points += (std::min(majorCount, minorCount)) * small;

return points;

}

};

[Vivek H]

*******************************************************************************

28Find the Index of the First Occurrence in a String42.7%Easy

*******************************************************************************

time complexity = O(n)

class Solution {

public:

    int strStr(string haystack, string needle) {

        if(needle.size() > haystack.size())

            return -1;

        for(int i=0; i<(haystack.size()-needle.size()+1); i++) {

            string str = haystack.substr(i, needle.size());

            if(str == needle) {

                return i;

            }

        }

        return -1;

    }

};

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/6e5e6d3c-35da-482d-879c-94d938181b89n%40googlegroups.com.

[Vivek H]

********************************************************************

942DI String Match78.8%Easy

********************************************************************

Time = O(n)

Space = O(n)

class Solution {

public:

    vector<int> diStringMatch(string s) {

        vector<int> V;

        vector<int> result;

        for(int i=0; i<=s.length(); i++)

            V.push_back(i);

        for(int i=0; i<s.length(); i++) {

            if(s[i] == 'D') {

                result.push_back(V.back());

                V.pop_back();

            } else {

                result.push_back(V.front());

                V.erase(V.begin());

            }

        }

        result.push_back(V.back());

        return result;

    }

   

};

On Sat, Jun 22, 2024 at 9:28 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--

[Vivek H]

************************************************************************************

1717Maximum Score From Removing Substrings47.1%Medium

************************************************************************************

Time = O(n)

Space = O(n)

Used stack to first use "ab" or "ba" dispensing on the points. 

if(points of "ab" > points of "ba")

 totalPoints = getPoints("ab", points of "ab") + getPoints("ba", points of "ba")

else

 totalPoints = getPoints("ba", points of "ba") + getPoints("ab",  points of "ab")

class Solution {

public:

    int getPoints(string& s, string str, int points) {

        int totalPoints = 0;

        vector<char> S;

        S.push_back(s[0]);

        //cout << S.back() << endl;

       

        for (int i = 1; i < s.size(); i++) {

            if (str == "ba") {

                if (S.size() > 0 && S.back() == 'b' && s[i] == 'a') {

                    totalPoints += points;

                    S.pop_back();

                } else {

                    S.push_back(s[i]);

                }

            } else {

                if (S.size() > 0 && S.back() == 'a' && s[i] == 'b') {

                    totalPoints += points;

                    S.pop_back();

                } else {

                    S.push_back(s[i]);

                }

            }

        }

        string temp;

        for (int i = 0; i < S.size(); i++) {

            temp += S[i];

        }

        s = temp;

        return totalPoints;

    }

    int maximumGain(string s, int x, int y) {

        size_t index;

        int maxPoint, minPoint;

        string minString, maxString;

        int points = 0;

        if (x > y) {

            maxPoint = x;

            minPoint = y;

            maxString = "ab";

            minString = "ba";

        } else {

            maxPoint = y;

            minPoint = x;

            maxString = "ba";

            minString = "ab";

        }

        points = getPoints(s, maxString, maxPoint) + getPoints(s, minString, minPoint);

        //cout << "points:" << points << " s:" << s << endl;

        return points;

    }

};

On Sat, Jun 22, 2024 at 9:28 AM daryl...@gmail.com <daryl...@gmail.com> wrote:

--