1653. Minimum Deletions to Make String Balanced #

Problem #

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

Problem Summary #

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. We say s is balanced when 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.

Solution Ideas #

• Given a string, we need to delete the minimum number of characters so that all letters a come before all letters b.
• An easy-to-think-of approach is DP. Define dp[i] as the minimum number of deletions needed to make the substring in the index range [ 0, i ] balanced. When s[i] == 'a', there are 2 cases. One is that everything before s[i] is in the form [aa……aa]; in this case, we only need to delete all the letters b among them. The other case is that there are both letters a and letters b before s[i], namely [aaa……abb……b]; in this case, we need to consider dp[i-1]. The current letter is a, so we must delete this letter a to maintain the situation where there is a segment of letters b before it. When s[i] == 'b', whether it is the [aa……aa] case or the [aaa……abb……b] case, the current letter b can be directly appended to the end, and the entire string can still be balanced. So the state transition equations are dp[i+1] = min(dp[i] + 1, bCount), s[i] == 'a', and dp[i+1] = dp[i], s[i] == 'b'. The final answer is in dp[n]. Since the recurrence between adjacent terms only uses the previous term once, we can also optimize the space by using one variable to store the result of the previous term. See Solution 1 for the optimized code.
• This problem also has a simulation approach. The problem asks for the minimum number of characters to delete, which means finding a “critical point”: delete all letters b to the left of this critical point, and delete all letters a to the right of this critical point. Among all “critical points”, find the minimum number of deletions. See Solution 2 for the code implementation.

Code #

package leetcode

// Solution 1 DP
func minimumDeletions(s string) int {
	prev, res, bCount := 0, 0, 0
	for _, c := range s {
		if c == 'a' {
			res = min(prev+1, bCount)
			prev = res
		} else {
			bCount++
		}
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// Solution 2 Simulation
func minimumDeletions1(s string) int {
	aCount, bCount, res := 0, 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'a' {
			aCount++
		}
	}
	res = aCount
	for i := 0; i < len(s); i++ {
		if s[i] == 'a' {
			aCount--
		} else {
			bCount++
		}
		res = min(res, aCount+bCount)
	}
	return res
}