Great vid, thank you 💪 I think it is not trivial why the greedy algorithm gives the optimal result. The challenge is to prove that removing e.g. one “ab” doesn’t ruin a potential goldmine of getting “bbbaaa” later.
Please create course of Math There are many people who does not come in software industry from math background especially in India where people do BCA / MCA to be in software industry so we can learn math and also improve logical thinking.
Here I was thinking how to handle "ab" after 2nd phase and the "Proof of contradiction" just blew my mind! You should definitely do a course on discrete math
awesome proof by contradiction . wondering if you have the problem for this kind of problem that asking for optimal scores after modify given data (str, tree, graph, etc), sometime, it's solved by DP/BFS.
I actually managed to make a single-pass solution that doesn't require mutating the input string OR using any intermediate data structure, just 3 integers. For each section of "a" and "b" strings, we can basically just keep a counter of the "ideal first element"s, of the "ideal second elements"s, and of the "ideal pairs" as we iterate. As we iterate, we try to greedily create as many "ideal pairs" as we can. We do this according to this simple rule: If we encounter an "ideal second element", then we check to see if the "ideal first element" counter is at least 1. If it is, then we can form an ideal pair, so we increase the "ideal pair" count by 1, and take away 1 "ideal first element" (since it is consumed to make the pair). If we have reached an ideal second element but we have NO ideal first elements, then we simply increase the increase the "ideal second element" counter. Finally, if we have an ideal first element, we just increment that counter no matter what. Finally, at the end, we know that for any pair that wasn't made into an ideal pair, it must be a non-ideal pair, so we just take "ideal points * ideal pairs + min(ideal first element, ideal second element) * nonideal points". Here is the code in Rust: ``` pub fn maximum_gain(s: String, x: i32, y: i32) -> i32 { let (ideal_start, ideal_points, other_points) = if x > y { ('a', x, y) } else { ('b', y, x) }; s.split(|c| c != 'a' && c != 'b') .map(|char_section| { let (start_count, end_count, ideal_pairs) = char_section.chars() .fold((0, 0, 0), |(start_count, end_count, ideal_pairs), c| match (start_count, c == ideal_start) { (0, false) => (start_count, end_count + 1, ideal_pairs), (_, false) => (start_count - 1, end_count, ideal_pairs + 1), _ => (start_count + 1, end_count, ideal_pairs) } ); start_count.min(end_count) * other_points + ideal_pairs * ideal_points }) .sum() } ```
i would love a course of proof by contradiction and proof by like counter example and other types of proofs and generally just algebra, i think it actually requires reasoning just like algorithms and will actually help in the long run :)
How do you know when choosing a greedy approach that there will never be a case where the greedy choice produces a suboptimal result in the end? I.e you chose "ab" because it is higher point, but that actually causes an output that produces a suboptimal result? Thats where I got stuck with this problem
Actually, you didn't prove that taking all 'ab' first is the optimal solution. You just proved that having done that you will not get any 'ab' at the second stage.
The proof wasn't about taking "ab" first, it was about eliminating all "ab" and "ba" in two phases, regardless of which we choose first. And yes, technically i didn;t do a formal proof, i dont think anyone wants to see that. but let me ask you, whats the difference between "ab" and "ba"? Aren't they symetrical? If we took "ba" first (assuming it has the higher score) we would end up with the same result. Try it if you dont believe me. :)
@@NeetCodeIO At 14:45 you're speaking about proving greedy algorithms, and my point is you didn't provide the proof. Sorry if you didn't mean that. Let's suppose 'ab' has the most score. Then what if removing 'ba' before all 'ab''s are removed could form a new pair and give better total score? One have to prove this wrong in order to prove that a greedy algorithm gives an optimal solution.
@@finemechanic this is proved by using the same method in the video, taking all cases, axxa, axxb etc. Once you strike out each case, you would realize taking the maximum pair first has to be the optimal solution and any other choice would lead to lower points.
yep, proud of the fact that I was able to think of a leetcode medium problem solution in less than 2 minutes(solution accepted). My approach was, iterate over the string character by character, if the current char is the same as that of the high value string, and the next char is same as that of the high value string, we skip them and add the high value score sum. Once we are done with the high value string we then move to the low value once repeating the process. By doing this, the problem can be easily solved.
I'm so frustrated that I thought of the exact solution you explained, the idea about stack and that we can first eliminate most expensive substrings and then others, but couldn't understand how to code it.... I got stuck when the idea which you proved can not exist by contradiction came to my mind
I somehow solved it in constant space in python. What do you think? class Solution: def maximumGain(self, s: str, x: int, y: int) -> int: a_count = b_count = 0 res = 0 for c in s: if x >= y: if c == 'a': a_count += 1 elif c == 'b': if a_count > 0: a_count -= 1 res += x else: b_count += 1 else: res += y * min(a_count, b_count) a_count = b_count = 0 else: if c == 'b': b_count += 1 elif c == 'a': if b_count > 0: b_count -= 1 res += y else: a_count += 1 else: res += x * min(a_count, b_count) a_count = b_count = 0 res += min(x, y) * min(a_count, b_count) return res
My first instinct was to solve it with dp. I did code the solution but it was brute force. Is it ok? Or do I have to come up with this optimal approach at once. will solving this question in brute force manner will indicate to the interviewer that I am good enough?
## SOLN FOR LIST OPTIMIZED O(1) space class Solution: def maximumGain(self, s: str, x: int, y: int) -> int: if x > y: l, r = 'a', 'b' else: l, r = 'b', 'a' x, y = y, x
# assume ab > ba # a XXX b # XXX is some eliminations of ba, like baba bbaa etc. notice the first and last char of XXX is b and a respectively, so they must have been eliminated in first trial # why choosing the larger valued one is preferred? the only case it is worse is that we give up >= 2 smaller ones, but thats notpossible. worse case is smth like baba. using ab won't make us miss > 1 ba s = list(s) res = 0 prev = -1 for i in range(len(s)): if prev != -1 and s[prev] == l and s[i] == r: prev -= 1 res += x else: s[prev+1] = s[i] prev += 1 pprev = -1 for i in range(prev+1): if pprev != -1 and s[pprev] == r and s[i] == l: pprev -= 1 res += y else: s[pprev + 1] = s[i] pprev += 1
class Solution { StringBuilder left; public int maximumGain(String s, int x, int y) { int ans=0; left=new StringBuilder(s); if(x>y){ ans+=takeAway("ab")*x; ans+=takeAway("ba")*y; } else{ ans+=takeAway("ba")*y; ans+=takeAway("ab")*x; } return ans; } public int takeAway(String sub){ int i=left.indexOf(sub); int c=0; while(i>=0){ c++; left.delete(i, i + 2); i=left.indexOf(sub); } return c; } } TLE
a variation of the O(1) space solution is in the corresponding leetcode editorial, but it can only be done in langs with a mutable string parameter s like c++ and rust, but python and java have an immutable string parameter s
Video req : " proof by contradiction "
Proof by contradiction was just perfect!!! Seriously a GOATed video of yours!! Keep making more :)
Ur explanation was phenomenal
Terrific explanation ! Love how in-depth you went. Too good.
do make the course on discrete maths . it will be awesome learning from you. ❤❤
This video cleared all my doubts that I had after seeing the editorials on leetcode. Great job bro ! keep it up ! Subscribed and liked !
Pure talent! Thanks for explaining in-depth and iterating through your approach! Amazed by your work you do!
13:45 oh my god😂😂😂😂😭😭 you are awesome
My job is solving LC problems but my true love is mathematics ❤️ ... maybe in the next life
@@NeetCodeIO lets do that discrete mathematics course then
WOW WOW WOW WOW this is my favorite video of yours of ALL TIME. I have tears. PURE ART.
Great vid, thank you 💪 I think it is not trivial why the greedy algorithm gives the optimal result. The challenge is to prove that removing e.g. one “ab” doesn’t ruin a potential goldmine of getting “bbbaaa” later.
Please create course of Math
There are many people who does not come in software industry from math background
especially in India where people do BCA / MCA to be in software industry
so we can learn math and also improve logical thinking.
Here I was thinking how to handle "ab" after 2nd phase and the "Proof of contradiction" just blew my mind!
You should definitely do a course on discrete math
mind blowing explanation
I think it would be cool if u showed code in like c++ or some other language for the O(1) space solution. Awesome video!!
It will be there on his website in the All section
awesome proof by contradiction . wondering if you have the problem for this kind of problem that asking for optimal scores after modify given data (str, tree, graph, etc), sometime, it's solved by DP/BFS.
damn, this was a tuff question for a medium tag!
thanks for the explanation
Amazing explanation!
I actually managed to make a single-pass solution that doesn't require mutating the input string OR using any intermediate data structure, just 3 integers. For each section of "a" and "b" strings, we can basically just keep a counter of the "ideal first element"s, of the "ideal second elements"s, and of the "ideal pairs" as we iterate. As we iterate, we try to greedily create as many "ideal pairs" as we can. We do this according to this simple rule: If we encounter an "ideal second element", then we check to see if the "ideal first element" counter is at least 1. If it is, then we can form an ideal pair, so we increase the "ideal pair" count by 1, and take away 1 "ideal first element" (since it is consumed to make the pair). If we have reached an ideal second element but we have NO ideal first elements, then we simply increase the increase the "ideal second element" counter. Finally, if we have an ideal first element, we just increment that counter no matter what. Finally, at the end, we know that for any pair that wasn't made into an ideal pair, it must be a non-ideal pair, so we just take "ideal points * ideal pairs + min(ideal first element, ideal second element) * nonideal points". Here is the code in Rust:
```
pub fn maximum_gain(s: String, x: i32, y: i32) -> i32 {
let (ideal_start, ideal_points, other_points) = if x > y {
('a', x, y)
} else {
('b', y, x)
};
s.split(|c| c != 'a' && c != 'b')
.map(|char_section| {
let (start_count, end_count, ideal_pairs) = char_section.chars()
.fold((0, 0, 0), |(start_count, end_count, ideal_pairs), c|
match (start_count, c == ideal_start) {
(0, false) => (start_count, end_count + 1, ideal_pairs),
(_, false) => (start_count - 1, end_count, ideal_pairs + 1),
_ => (start_count + 1, end_count, ideal_pairs)
}
);
start_count.min(end_count) * other_points + ideal_pairs * ideal_points
})
.sum()
}
```
God level explanation 🔥🔥
Wow, just phenomenal explanation.
Just epic. Thanks a lot Neetcode
Damn, Navi got me so excited at 14:00
14:20 🤯 Literally
i would love a course of proof by contradiction and proof by like counter example and other types of proofs and generally just algebra, i think it actually requires reasoning just like algorithms and will actually help in the long run :)
Neetcode please make a course on discrete Mathematics I really want to learn more about it please please
goated explanantion
Any hint at when your python for interviews course is coming out? I'm really excited for it
13:33
bruh become Jett when killing this problem.
Navdeep, you did indeed blow my mind haha. Good explanation
How do you know when choosing a greedy approach that there will never be a case where the greedy choice produces a suboptimal result in the end? I.e you chose "ab" because it is higher point, but that actually causes an output that produces a suboptimal result? Thats where I got stuck with this problem
great explanation man!!
discrete math course would be awesome👍👍
this is great
Strings are mutable in c++ (c++ mention)
genuinely S tier video
we are very much interested my guy, anything you wanna teach, just go for it, hehe
Let's go for DM course
How u become this good at explaining
No secret tips, it's just Ive explained about 600 LC problems. I think anyone would get better at explaining if they did that
Actually, you didn't prove that taking all 'ab' first is the optimal solution. You just proved that having done that you will not get any 'ab' at the second stage.
Yup realised that too. Felt abit of dunning kruger
The proof wasn't about taking "ab" first, it was about eliminating all "ab" and "ba" in two phases, regardless of which we choose first.
And yes, technically i didn;t do a formal proof, i dont think anyone wants to see that. but let me ask you, whats the difference between "ab" and "ba"? Aren't they symetrical? If we took "ba" first (assuming it has the higher score) we would end up with the same result. Try it if you dont believe me. :)
@@NeetCodeIO At 14:45 you're speaking about proving greedy algorithms, and my point is you didn't provide the proof. Sorry if you didn't mean that. Let's suppose 'ab' has the most score. Then what if removing 'ba' before all 'ab''s are removed could form a new pair and give better total score? One have to prove this wrong in order to prove that a greedy algorithm gives an optimal solution.
@@finemechanic this is proved by using the same method in the video, taking all cases, axxa, axxb etc. Once you strike out each case, you would realize taking the maximum pair first has to be the optimal solution and any other choice would lead to lower points.
Thankyou so much for your daily videos, i managed tto score an intern due to this, thankyou so soo muchhhh🥹🥹
LETS GOOO
love the profile pic
@@NeetCodeIO Thanks 😆😆
@@NeetCodeIO your reply made my dayyy 🥹🥹
yep, proud of the fact that I was able to think of a leetcode medium problem solution in less than 2 minutes(solution accepted). My approach was, iterate over the string character by character, if the current char is the same as that of the high value string, and the next char is same as that of the high value string, we skip them and add the high value score sum. Once we are done with the high value string we then move to the low value once repeating the process. By doing this, the problem can be easily solved.
O(1) space complexity solution is interesting!
very nice explanation...
Mind = blown 😶🌫️
Interesting question!
Please make proof by contradiction videos available. Thank you. 🙏
I'm so frustrated that I thought of the exact solution you explained, the idea about stack and that we can first eliminate most expensive substrings and then others, but couldn't understand how to code it.... I got stuck when the idea which you proved can not exist by contradiction came to my mind
Actually I coded it after your explanation without looking at your solution. Thanks!
My Same logic in C++ runs slower, why becoz of too many time of reverse string becoz of stack??
8:23 the berlin wall?
Yeah that's what came to my mind as well
Hey ! Can u explain how we will update score in space optimal solution?
proof by contradiction - We need it
imagine seeing this in an interview for the first time. how does one come up with a working solution and proof in 20 minutes?
A lot of practice
How did you determine that we need to use a stack for this solution? If I encounter a different question, how will I know when to use a stack?
If you didn’t think of a stack in this problem, you haven’t solved enough stack problems. Do more stack problems.
I somehow solved it in constant space in python.
What do you think?
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
a_count = b_count = 0
res = 0
for c in s:
if x >= y:
if c == 'a': a_count += 1
elif c == 'b':
if a_count > 0:
a_count -= 1
res += x
else:
b_count += 1
else:
res += y * min(a_count, b_count)
a_count = b_count = 0
else:
if c == 'b': b_count += 1
elif c == 'a':
if b_count > 0:
b_count -= 1
res += y
else:
a_count += 1
else:
res += x * min(a_count, b_count)
a_count = b_count = 0
res += min(x, y) * min(a_count, b_count)
return res
this is not correct. how are you enforcing that the ab string is consecutive? also you are never modifying the input string
@@budderpenguin43 Its different approach from what neetcode has shown for the O(1) space solution
My first instinct was to solve it with dp. I did code the solution but it was brute force. Is it ok? Or do I have to come up with this optimal approach at once. will solving this question in brute force manner will indicate to the interviewer that I am good enough?
bro can you provide brute force solution cause my brute force one was getting wrong
No. Brute force is usually not enough. It is a good starting point tho
@@dhatrishdixit6004 I posted a link to my submission
strings are mutable in cpp so 0(n) gain is real
LFG discreet math video :D
Not gonna lie, mind blown!
bro did a full analysis
I would like a course on discrete maths
A typical greedy, but you need to make sure otherwise it's a DP
🙌🙌 You are Genius 🫡🙌🎩
discrete maths please
I can only think of dp solution. Greedy feels hard
can someone explain to me why it doesn't work in python? I know that string is immutable, but can't you still convert it to an array
You will have O(n) space complexity right at the moment of building the array.
My brain is damaged this morning.
❤
## SOLN FOR LIST OPTIMIZED O(1) space
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
if x > y:
l, r = 'a', 'b'
else:
l, r = 'b', 'a'
x, y = y, x
# assume ab > ba
# a XXX b
# XXX is some eliminations of ba, like baba bbaa etc. notice the first and last char of XXX is b and a respectively, so they must have been eliminated in first trial
# why choosing the larger valued one is preferred? the only case it is worse is that we give up >= 2 smaller ones, but thats notpossible. worse case is smth like baba. using ab won't make us miss > 1 ba
s = list(s)
res = 0
prev = -1
for i in range(len(s)):
if prev != -1 and s[prev] == l and s[i] == r:
prev -= 1
res += x
else:
s[prev+1] = s[i]
prev += 1
pprev = -1
for i in range(prev+1):
if pprev != -1 and s[pprev] == r and s[i] == l:
pprev -= 1
res += y
else:
s[pprev + 1] = s[i]
pprev += 1
return res
🐐
class Solution {
StringBuilder left;
public int maximumGain(String s, int x, int y) {
int ans=0;
left=new StringBuilder(s);
if(x>y){
ans+=takeAway("ab")*x;
ans+=takeAway("ba")*y;
}
else{
ans+=takeAway("ba")*y;
ans+=takeAway("ab")*x;
}
return ans;
}
public int takeAway(String sub){
int i=left.indexOf(sub);
int c=0;
while(i>=0){
c++;
left.delete(i, i + 2);
i=left.indexOf(sub);
}
return c;
}
}
TLE
beauty
Feels like someone annoyed him about this problem, especially the phase 2 😂😂
pls provide codein other languages cpp java or atleast give your code in description
a variation of the O(1) space solution is in the corresponding leetcode editorial, but it can only be done in langs with a mutable string parameter s like c++ and rust, but python and java have an immutable string parameter s
Give us Discrete Math 🧠🧠
it was a boo boo
Great explanation ❤