Minimum Deletions to Make String Balanced - Leetcode 1653 - Python

[@jayrathod9271]

I applied the same approach. This is a rare moment where I could solve it myself in 1.5 hr. Thank you @NeetCodeIO for such a great explanation every day.

[@thenameisafsal]

The question was not understandable to me initially, but your solution has cleared it up and now I'm clear at it. Thanks man!

[@yuvarajyuvi9691]

We don't even need to track a_count , whenever we encounter "a" we can check if there is a b before and decrement b_count and add 1 to result def minimumDeletions(self, s: str) -> int: res = 0 bc = 0 for i in range(len(s)): if s[i] == "b": bc += 1 elif s[i] == "a" and bc > 0: bc -= 1 res += 1 return res

[@michaelroditis1952]

Exactly this is the fastest solution

[@ZaneMouakket]

At first I did a 2d DP solution with one dimension being the start and one being the end and the number stored in the matrix is how many had to be deleted for everything between start and end to be balanced. I always assumed if there is a solution like this that it would be the fastest, but no matter how I optimized it, it either got TLE or MLE. Thank you for explaining the correct solution so well.

[@jamestwosheep]

I managed to solve this one with a stack in O(n) time complexity, but I really like how you managed to get that O(1) space complexity solution. 👏👏

[@wasd3108]

there's a better solution with 1 iteration only

[@pcgaming6597]

For Java people : public int minimumDeletions(String s) { int n=s.length(); int countMin=n; int countRight_a=0; for(int i=0;i

[@vm1662]

The solution is beautiful!!!! Thank you.

[@yang5843]

Was waiting for this, thank you

[@kareni7572]

Calculating the result between the if's is interesting. Understood after running it myself

[@michaelroditis1952]

You can do it with one loop You keep track of the b_count and each time you encounter an 'a' while b_count is greater than 0, you add 1 to the result and subtract 1 from b_count

[@keyurparmar2595]

Yeh, correct Thank you for showing me a new direction to think

[@michaelroditis1952]

@@keyurparmar2595 of course! 😁 If you want I can further explain this

[@qulinxao]

v,w=[0,0],lambda x:x=='a' for c in map(w,s):v[c]=max(v[-c:])+1 return len(s)-max(v)

[@jotrades26]

I like this, you gave a short about negate the problem and it works here even the previous one 👌👌👌

[@nirmalgurjar8181]

from last 2 POTDs invert actually became mid, instead of solving from top-down or bottom-up consider current element as mid element and start building solution gives as optimal/better clean solution.

[@САИДАМАГОМЕДДИБИРОВА]

👍👍👍👍👍thank you!

[@sagnikbiswas3268]

Iterate over minimal B index. Clear A’s to the right and clear all B’s to the left. Simple

[@qulinxao]

class Solution: def minimumDeletions(self, s: str) -> int: v=[0,0] for c in [ord(c)-97 for c in s]: v[c]=max(v[0],v[c])+1 return len(s)-max(v)

[@yang5843]

Java Solution class Solution { public int minimumDeletions(String s) { int a = s.replaceAll("b","").length(); int b = 0; int res = a; for ( char c : s.toCharArray() ) { if ( c == 'a' ) a--; else if ( c == 'b' ) b++; res = Math.min(res,a+b); } return res; } }

[@MP-ny3ep]

Beautiful explanation. Thank you.

[@kawaljeetsingh1657]

Thanks, Navdeep....

[@omkara477]

I love neetcode.. 2 minutes into the video and im like ya i can take it from here thanx man! 😂😂

[@pratyushthakur8478]

I am sad I couldn't solve this without looking at hints :(

[@AJK-a2j00k4]

I got fucked with edge cases even after looking at the hints and came here :(

[@kgCode658]

int n = s.size(); vector left(n,0); vector right(n,0); int cntLeft = 0; int cntRight = 0; for(int i=0 ; i

[@aashishbathe]

class Solution: def minimumDeletions(self, s: str) -> int: res = count = 0 for char in s: if char == 'b': count += 1 else: if count: res += 1 count -= 1 return res THIS also seems to work somehow, one pass solution..

[@haotang4717]

This seems better. Related to parentheses problem. Each reversion of b and a needs at least one deletion.

[@ayobrrr]

i am so dumb, as soon as you said 0:43 - we can draw partition, i straightly went back and implemented lol 😂😂

[@dan_____]

You can actually view this problem in a different way. All we care about is the minimum amount of deletions, or CONFLICTS in the string. A conflict happens when a B comes before an A. This means every appearance of a B is a POTENTIAL conflict. A potential conflict is solidified when we encounter an A. When that happens, we can increment our answer and decrease the amount of potential conflicts.

[@王瀚君-c3j]

Thank you man

[@qulinxao]

clearer:class Solution: def minimumDeletions(self, s: str) -> int: v,w=[0,0],lambda x:x=='a' for c in map(w,s):v[c]=max(v[-c:])+1 return len(s)-max(v)

[@anandsahoo3711]

if anyone is wondering why the same solution doesn't work in java just change the length of res=a_count_right

[@venkatexplorermetturdam]

Bro please continue in python Thanks It makes me to learn more and start dsa channel ❤😊

[@greatfate]

not most optimal, there's a one pass solution which is also O(1) space

[@sourvad]

Very demotivated that I could not even approach this problem, not even a clue where to begin :(

[@samarthjain5015]

I'm surprised they haven't run out of "balanced" titles.

[@aadil4236]

Why am I alwasy thinking of DP!! I figured out the solution when kind of gave the hint at 3:00. God I'm stupid.

[@flamendless]

At work: implemented a very efficient code Boss: how do you know it's the most efficient without benchmarking? Me: it is, i promise. Trust me

[@md_pedia1]

why can't we just use a stack. every time we see an a followed by a b we could pop from the stack and increment res by 1. And it worked for me😐😐

[@ksvijayan06]

that is ba if ba pair exist remove and increment the count

[@ayushmandash948]

there's a test case that fails for the stack approach that I tried, "aaaaaabbbbabaaaabbabaaabbabbbaaabababaaaaaaabbaaabaaababaaabababa"

[@md_pedia1]

​@@ayushmandash948 try this: res=0 st=[] for i in s: if i=='a' and st: st.pop() res+=1 elif i=='b': st.append(i) return res

[@md_pedia1]

@@ayushmandash948 try this: res=0 st=[] for i in s: if i=='a' and st: st.pop() res+=1 elif i=='b': st.append(i) return res

[@shubham6523]

@@ayushmandash948 bro i tried with the stack soln and this testcase working with my soln

[@MehmetDemir-xi3yy]

I know this solution gives correct output but for intermediate steps I think it does not. For example s = "bbba", when you calculate for last b, there are 2 b left and 1 a right so you found 3 operation. But we can just delete "a" and good to go. So I am saying at the end of the algorithm we find correct result but not in intermediate ones.

[@pritampadhan5977]

Bro the point is where we place the pointer such that we have to delete minimum characters. In your example in suitable when we keep the pointer at 1st 'b' and that's the solution.

[@MehmetDemir-xi3yy]

​@@pritampadhan5977 I couldnt get it 🤔

[@MehmetDemir-xi3yy]

I repeat, I understood the solution but I couldnt understand or it doesnt make sense for intermediate result. Lets think more basic example. S="bbb" when we calculate for 3rd "b" there are 2b and zero a. So we find 2 operation. But thats not the case. I am saying this because when I solve questions if it doesnt make sense at any point I just give up that solution

[@DNKF]

This video is a must have before my everyday dinner. =] I have a suggestion for future Java, C++ or other languages classes. Since we have most videos in Python and Python has lot of good tricks, if you can make "conversion" class like Python tricks to Java or C++, it would be great for beginner.

[@dss963]

I don't think this solution is correct in all aspects, .Why should someone delete all "b"s on left and all "a"s on right? Why cant we delete all chars of particular type on one side , but not both type, even that satisfy the condition and is the minimum btw?

[@AJK-a2j00k4]

the code he wrote includes that as well bro! maybe try these test case : "bbbbbbbaa"

[@zweitekonto9654]

Because that's what will give you the minimum? If you also start deleting characters of the other type that had no problem if they were left as it is, you are unnecessarily increasing your number of operations.

[@minhtungbui2002]

Another solution for this problem is Stack =))

[@ajitpalsingh606]

Doing after 10 hr of driving

[@corrogist692]

did it with a sliding window with O(n)&O(1), then saw a super smart 8 lines solution up there lol ``` ans, count = 0, 0 for i in s: if i == 'b': count += 1 elif count: ans += 1 count -= 1 return ans ```

[@sahilmalik8670]

mate can u explain the elif line

[@janaSdj]

Nice

[@yang5843]

​@@sahilmalik8670if u see a 'a' and there was already a 'b', you have to increment res to remove one of the the 'b's

[@corrogist692]

@@sahilmalik8670 try to use an example and simulate the iterations, basically it is keeping track of the minimum of the rolling 'a's/'b's

[@AJK-a2j00k4]

how did u do it with sliding window btw?

[@dipakmaity2205]

first comment sir

[@EdificioPepinutalini]

you like to code, i like to create. This is why ur so scared of LLMs.

[@NeetCodeIO]

you got me there