1717. Maximum Score From Removing Substrings | Why not DP | Greedy | Stack | 2 Pointer | 2 Approach

In this video, I'll talk about how to solve Leetcode 1717. Maximum Score From Removing Substrings | Why not DP | Greedy | Stack | 2 Pointer | 2 Approaches

Let's Connect:

About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)

✨ Timelines✨
0:00 - Spoiler & Bhek
00:45 - Problem Explanation
1:31 - DP Approach
3:44 - Why Stack?
8:00 - Why Greedy ? (Proof)
11:03 - Stack & Greedy Dry Run
14:00 - Code Explanation
18:46 - 2 Pointer Dry Run
27:52 - Code Explanation

✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[ARYANMITTAL]

So, everyone asks to not put spoiler in titles, I put this on the basis of my experience with other leetcode tutorials of my time (eg: 3 years back, when i was preparing for internship, whenever i search for any leetcode problem, there used to come 1 channel's video most often, i'll not name it, though it was good, but as soon as there used to hard follow up of any problem or hard variant, he used to skip it & i hated that part everytime, that atleast write in beginning or tell you will teach very basic stuff)
.
Thus, i write in title or tell in beginning that what all you will get from video & look for that part accordingly. (Why DP, was very specific to me! I just thought, somehow DP was intuitive to me but later realised that it can't solve, so yeah discussed that too 🌚)

[sanket]

O(1) space approach :
Suppose y > x in that case we have to remove first "ba" For that we can traverse the string with keeping count of b now whenever a occur & b's count > 0 we have found "ba" So increase the ans, decrease the count for b. Also we need to reset the b's count when any other char occur like bbbbx.
Now then all the "ba" cases are done now we need to remove the "ab" cases, so for that we need all a that didn't make it in "ba". Basically all a for which there was no previous b to make a "ba" pattern, these all a can make ab pair so count all such a's and then increase the ans by min(cn(a), cn(b)) * min(x, y).
This solution got accepted if anyone is looking for o(1) space approach

[kgjr.]

I rely wish your channel should grow because in todays world where other youtube channels as selling dreams this man is rely spreading real content and with huge amount of consistency

[krutikadave]

maqsad string 😁 this channel is the OG of daily challenge leetcode!

[rev_krakken]

I am happy today, since i think this is the first time i came up with an algorithm on my own and the fact that i did not consider any existing template and stuff before coding the solution, and I was able to beat 100% with my solution

[varunjain]

Thankyou so much bro amazing explanation💯

[akshaanshsrivastava]

Thanks Sir. These types of videos help me with intuition and approach..

[IK-xkex]

Thank you! It's interesting technique with modifying the string in place. Hmm

[advaithmahendrakar]

class Solution {
public int maximumGain(String s, int x, int y) {

Stack<Character> st = new Stack<>();
int ans =0;
for(int i =0 ; i < s.length() ; i++){
System.out.println(st);
if(s.charAt(i) == 'a'&& !st.isEmpty() && st.peek() == 'b' ){
if(y > x){
st.pop();
ans += y;
System.out.println(ans);
}else{
st.push(s.charAt(i));
}
}else if(s.charAt(i) == 'b' && !st.isEmpty() && st.peek() == 'a'){
if(y > x){
st.push(s.charAt(i));
}else{
st.pop();
ans += x;
System.out.println(ans + "x>");
}
}else{
st.push(s.charAt(i));
}
}

while(!st.isEmpty()){
char ch = st.pop();
if(!st.isEmpty() && st.peek() == 'a' && ch == 'b'){
ans += x;
}else if(!st.isEmpty() &&st.peek() == 'b' && ch == 'a'){
ans += y;
}
}




return ans;
}
}

Why is this solution wrong please anyone explain?

[abhinavnarula]

Is the second approach some kind of pattern or is it only applicable to this question only?

[mayanktandon]

THIS IS LITERALLY BY FAR THE BEST F**ING EXPLANATION THERE
WALKED THROUGH THE THOUGHT PROCESS FROM THE BEGINNER POV TO OPTIMIZATION, LOVED IT ❤

[naamnhibataunga]

this was my solution :

class Solution {
public:

int point(string &s, string target, int p){
int total=0;
string str="";
for(char c:s){
if(!str.empty() && string(1, str.back()) + c==target){
str.pop_back();
total+=p;
}
else{
str+=c;
}
}
s=str;
return total;
}

int maximumGain(string s, int x, int y) {
string s1="ab", s2="ba";
if(y>x){
swap(s1, s2);
swap(x, y);
}
return point(s, s1, x)+point(s, s2, y);
}
};

[sriramadithya]

Hi Aryan,
I have been learning DSA for a month, and I am solving daily challenges in a leetcode, I used to see your videos for understanding a problem bro, Thanks for your work. But my question is when I see a problem I cannot solve it by myself. It feels like I am not improving anything 😞I always look for a solution. Did you have the same feeling when you were learning DSA, How did you overcome this?

[theerock-ei]

please solve leetcode 913 cat and mouse

[theerock-ei]

please solve leetcode 913 cat and mouse problem