You are given a string s consisting only of characters 'a' and 'b'.
You can delete any number of characters in s to make sbalanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.
Return the minimum number of deletions needed to make sbalanced.
Example 1:
Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").
Example 2:
Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.
Constraints:
1 <= s.length <= 105
s[i] is 'a' or 'b'.
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the minimum number of characters to be deleted in the first $i$ characters to make the string balanced. Initially, $f[0]=0$. The answer is $f[n]$.
We traverse the string $s$, maintaining a variable $b$, which represents the number of character 'b' in the characters before the current position.
If the current character is 'b', it does not affect the balance of the first $i$ characters, so $f[i]=f[i-1]$, then we update $b \leftarrow b+1$.
If the current character is 'a', we can choose to delete the current character, so $f[i]=f[i-1]+1$; or we can choose to delete the previous character 'b', so $f[i]=b$. Therefore, we take the minimum of the two, that is, $f[i]=\min(f[i-1]+1,b)$.
In summary, we can get the state transition equation:
We notice that the state transition equation is only related to the previous state and the variable $b$, so we can just use an answer variable $ans$ to maintain the current $f[i]$, and there is no need to allocate an array $f$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
/** * @param {string} s * @return {number} */varminimumDeletions=function(s){constn=s.length;constf=newArray(n+1).fill(0);letb=0;for(leti=1;i<=n;++i){if(s[i-1]==='b'){f[i]=f[i-1];++b;}else{f[i]=Math.min(f[i-1]+1,b);}}returnf[n];};
Solution 2: Enumeration + Prefix Sum
We can enumerate each position $i$ in the string $s$, dividing the string $s$ into two parts, namely $s[0,..,i-1]$ and $s[i+1,..n-1]$. To make the string balanced, the number of characters we need to delete at the current position $i$ is the number of character 'b' in $s[0,..,i-1]$ plus the number of character 'a' in $s[i+1,..n-1]$.
Therefore, we maintain two variables $lb$ and $ra$ to represent the number of character 'b' in $s[0,..,i-1]$ and the number of character 'a' in $s[i+1,..n-1]$ respectively. The number of characters we need to delete is $lb+ra$. During the enumeration process, we update the variables $lb$ and $ra$.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string $s$.