LeetCode 1653. Minimum Deletions to Make String Balanced Solution in Java, C++, Python & More | Explanation + Code

Description

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. 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 s balanced.

 

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 ← 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:

f[i]=\begin{cases} f[i-1], & s[i-1]='b'\ min(f[i-1]+1,b), & s[i-1]='a' \end{cases}

The final answer is f[n].

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).

PythonJavaC++GoTypeScriptJavaScript

class Solution: def minimumDeletions(self, s: str) -> int: n = len(s) f = [0] * (n + 1) b = 0 for i, c in enumerate(s, 1): if c == 'b': f[i] = f[i - 1] b += 1 else: f[i] = min(f[i - 1] + 1, b) return f[n](code-box)

class Solution { public int minimumDeletions(String s) { int n = s.length(); int[] f = new int[n + 1]; int b = 0; for (int i = 1; i <= n; ++i) { if (s.charAt(i - 1) == 'b') { f[i] = f[i - 1]; ++b; } else { f[i] = Math.min(f[i - 1] + 1, b); } } return f[n]; } }(code-box)

class Solution { public: int minimumDeletions(string s) { int n = s.size(); int f[n + 1]; memset(f, 0, sizeof(f)); int b = 0; for (int i = 1; i <= n; ++i) { if (s[i - 1] == 'b') { f[i] = f[i - 1]; ++b; } else { f[i] = min(f[i - 1] + 1, b); } } return f[n]; } };(code-box)

func minimumDeletions(s string) int { n := len(s) f := make([]int, n+1) b := 0 for i, c := range s { i++ if c == 'b' { f[i] = f[i-1] b++ } else { f[i] = min(f[i-1]+1, b) } } return f[n] }(code-box)

function minimumDeletions(s: string): number { const n = s.length; const f = new Array(n + 1).fill(0); let b = 0; for (let i = 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); } } return f[n]; }(code-box)

/** * @param {string} s * @return {number} */ var minimumDeletions = function (s) { const n = s.length; const f = new Array(n + 1).fill(0); let b = 0; for (let i = 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); } } return f[n]; };(code-box)

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.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def minimumDeletions(self, s: str) -> int: lb, ra = 0, s.count('a') ans = len(s) for c in s: ra -= c == 'a' ans = min(ans, lb + ra) lb += c == 'b' return ans(code-box)

class Solution { public int minimumDeletions(String s) { int lb = 0, ra = 0; int n = s.length(); for (int i = 0; i < n; ++i) { if (s.charAt(i) == 'a') { ++ra; } } int ans = n; for (int i = 0; i < n; ++i) { ra -= (s.charAt(i) == 'a' ? 1 : 0); ans = Math.min(ans, lb + ra); lb += (s.charAt(i) == 'b' ? 1 : 0); } return ans; } }(code-box)

class Solution { public: int minimumDeletions(string s) { int lb = 0, ra = count(s.begin(), s.end(), 'a'); int ans = ra; for (char& c : s) { ra -= c == 'a'; ans = min(ans, lb + ra); lb += c == 'b'; } return ans; } };(code-box)

func minimumDeletions(s string) int { lb, ra := 0, strings.Count(s, "a") ans := ra for _, c := range s { if c == 'a' { ra-- } if t := lb + ra; ans > t { ans = t } if c == 'b' { lb++ } } return ans }(code-box)

function minimumDeletions(s: string): number { let lb = 0, ra = 0; let n = s.length; for (let i = 0; i < n; ++i) { if (s[i] === 'a') { ++ra; } } let ans = n; for (let i = 0; i < n; ++i) { ra -= s[i] === 'a' ? 1 : 0; ans = Math.min(ans, lb + ra); lb += s[i] === 'b' ? 1 : 0; } return ans; }(code-box)

/** * @param {string} s * @return {number} */ var minimumDeletions = function (s) { let lb = 0, ra = 0; let n = s.length; for (let i = 0; i < n; ++i) { if (s[i] === 'a') { ++ra; } } let ans = n; for (let i = 0; i < n; ++i) { ra -= s[i] === 'a' ? 1 : 0; ans = Math.min(ans, lb + ra); lb += s[i] === 'b' ? 1 : 0; } return ans; };(code-box)