1717. Maximum Score From Removing Substrings - Day 12/31 Leetcode July Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!
Problem: leetcode.com/problems/maximum...
Twitch: / larryny
Discord: / discord
Instagram: / larrysomewhere
#leetcode #coding #programming

[@Algorithmist]

Did you get all the scores?

[@redfinance3403]

No, I'm very bad with these stack problems.

[@tuandino6990]

If the interviewer ask me why I use greedy for this problem, I think i cant explain

[@user-vq8zo4bi3b]

When choosing between 'ab' or 'ba', there will always be a shared 'a' or 'b' between the two options. An interesting thing happens in this process. For example, '...aba...' will always become '...a...' after removing, regardless of whether you choose to remove 'ab' or 'ba'. Similarly, '...bab...' will always become '...b...'. This behavior extends to longer chunks of 'ab' or 'ba'. Therefore, you should choose to remove 'ab' or 'ba' based on the points x and y.

[@Algorithmist]

that is the invariant that I couldn't figure out, thanks!

[@rohitkumarpilania94]

So what id did was:
1) Remove the string that provides more i.e ab if x > y or vice versa
2) when you are done with this, you'll have a stack with potential points left in it
Now see:
if x > y:
you'll never find "ab" in stack leftover cause I deleted all of them
.:. possible stacks are: [aaaaa], [bbbaaa], [bbbbbbbba]
ans += y*min(a,b)
if y > x:
you'll never find "ba" in stack leftover cause I deleted all of them
.:. possible stacks are: [aaaaaaaa], [aabbbb], [aaaaaab]
ans += x*min(a,b)

[@nox3042]

Still dont understand why hint 1 from the subject is Always True.
But supposing this statement true, it can be solved like this
`return max(f(s, x, y, 'a', 'b'), f(s, y, x, 'b', 'a')); ` without inversing all the a's and b's

[@Hope-ck6hy]

Do you think i can use count() and replace() to replace the for loop you used?

[@Algorithmist]

Maybe? the thing is that you might have aabb which requires the stack

[@codenocode]

yes this was a very specific problem. It's a experiment and make it work type of problem.