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.
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() } ```
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
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.
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 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.
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?
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 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
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
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
## 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
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
