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.
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
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.
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.
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
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; } }
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..
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.
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.
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.
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.
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
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 ```
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?
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.
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.
The question was not understandable to me initially, but your solution has cleared it up and now I'm clear at it. Thanks man!
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. 👏👏
there's a better solution with 1 iteration only
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
Exactly this is the fastest solution
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.
I like this, you gave a short about negate the problem and it works here even the previous one 👌👌👌
For Java people :
public int minimumDeletions(String s) {
int n=s.length();
int countMin=n;
int countRight_a=0;
for(int i=0;i
Calculating the result between the if's is interesting. Understood after running it myself
The solution is beautiful!!!! Thank you.
I am sad I couldn't solve this without looking at hints :(
I got fucked with edge cases even after looking at the hints and came here :(
I love neetcode.. 2 minutes into the video and im like ya i can take it from here thanx man! 😂😂
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!
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
Yeh, correct
Thank you for showing me a new direction to think
@@keyurparmar2595 of course! 😁
If you want I can further explain this
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)
Was waiting for this, thank you
Iterate over minimal B index. Clear A’s to the right and clear all B’s to the left. Simple
int n = s.size();
vector left(n,0);
vector right(n,0);
int cntLeft = 0;
int cntRight = 0;
for(int i=0 ; i
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;
}
}
Beautiful explanation. Thank you.
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..
This seems better. Related to parentheses problem. Each reversion of b and a needs at least one deletion.
Bro please continue in python
Thanks
It makes me to learn more and start dsa channel ❤😊
Thanks, Navdeep....
i am so dumb, as soon as you said 0:43 - we can draw partition, i straightly went back and implemented lol 😂😂
I'm surprised they haven't run out of "balanced" titles.
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
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)
Thank you man
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.
if anyone is wondering why the same solution doesn't work in java just change the length of res=a_count_right
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😐😐
that is ba if ba pair exist remove and increment the count
there's a test case that fails for the stack approach that I tried, "aaaaaabbbbabaaaabbabaaabbabbbaaabababaaaaaaabbaaabaaababaaabababa"
@@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
@@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
@@ayushmandash948 bro i tried with the stack soln and this testcase working with my soln
Very demotivated that I could not even approach this problem, not even a clue where to begin :(
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)
not most optimal, there's a one pass solution which is also O(1) space
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.
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.
Another solution for this problem is Stack =))
For java folks
leetcode.com/problems/minimum-deletions-to-make-string-balanced/solutions/5560581/neetcode-java-greedy-solution/
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.
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.
@@pritampadhan5977 I couldnt get it 🤔
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
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
```
mate can u explain the elif line
Nice
@@sahilmalik8670if u see a 'a' and there was already a 'b', you have to increment res to remove one of the the 'b's
@@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
how did u do it with sliding window btw?
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?
the code he wrote includes that as well bro! maybe try these test case : "bbbbbbbaa"
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.
Doing after 10 hr of driving
you like to code, i like to create. This is why ur so scared of LLMs.
you got me there
first comment sir