Table of contents
Open Table of contents
Description
Question Link: LeetCode 1653
You are given a string s containing only a and b. The string is balanced when no b appears before a later a. Return the minimum number of characters to delete to make s balanced.
Constraints
s[i]is eitheraorb.
Idea
A balanced string has the shape a* b*: once a b appears, no a may follow. For a prefix, keep two values: the minimum deletions needed to balance it, and the number of bs seen so far.
When the next character is b, it can stay, so increment the b count. When it is a, either delete this a (one more deletion) or keep it and delete every earlier b. Take the cheaper choice:
s: a a b a b b
b seen: 0 0 1 1 2 3
min deletions:0 0 0 1 1 1
For aababb, the answer is one deletion: remove the middle a to get aabbb.
Complexity: Time , Space .
Prefix/suffix split
A second way is to try every split between the kept as and the kept bs. For a split at index i, delete the bs before i and the as from i onward. The remaining characters always have the balanced form a* b*. A suffix array counts the as to the right of each split, while a running count tracks bs on the left.
Complexity: Time , Space .
Java
package string;
/**
* <a href="https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/">LeetCode 1653</a>.
*/
public final class MinimumDeletionsToMakeStringBalanced {
private MinimumDeletionsToMakeStringBalanced() {}
/**
* One-pass dynamic programming. Time O(n), Space O(1).
*/
public static int minimumDeletions(String s) {
int deletions = 0;
int bCount = 0;
for (int i = 0; i < s.length(); i++) { // O(n) total: each character is processed once.
char c = s.charAt(i);
if (c == 'b') {
bCount++;
} else {
// Delete this 'a', or delete all earlier 'b's.
deletions = Math.min(deletions + 1, bCount);
}
}
return deletions;
}
/**
* Try every split between an all-'a' prefix and all-'b' suffix. Time O(n), Space O(n).
*/
public static int minimumDeletionsBySplit(String s) {
int n = s.length();
int[] suffixACount = new int[n + 1]; // O(n) extra space for suffix counts.
for (int i = n - 1; i >= 0; i--) { // O(n): build counts from right to left.
suffixACount[i] = suffixACount[i + 1] + (s.charAt(i) == 'a' ? 1 : 0);
}
int prefixBCount = 0;
int minDeletions = n;
for (int split = 0; split <= n; split++) { // O(n): evaluate all n + 1 splits.
minDeletions = Math.min(minDeletions, prefixBCount + suffixACount[split]);
if (split < n && s.charAt(split) == 'b') {
prefixBCount++;
}
}
return minDeletions;
}
}
Python
"""LeetCode 1653: minimum deletions to make a string balanced."""
class Solution:
def minimumDeletions(self, s: str) -> int:
"""One-pass DP; O(n) time and O(1) auxiliary space."""
deletions = 0
b_count = 0
for char in s: # O(n) time; each character is processed once.
if char == "a":
# Keep this 'a' by deleting earlier 'b's, or delete this 'a'.
deletions = min(deletions + 1, b_count)
else:
b_count += 1
return deletions
def minimumDeletionsBySplit(self, s: str) -> int:
"""Return the minimum deletions by checking every balanced split."""
n = len(s)
suffix_a = [0] * (n + 1) # O(n) auxiliary space.
for index in range(n - 1, -1, -1): # O(n) time to count suffix 'a's.
suffix_a[index] = suffix_a[index + 1] + (s[index] == "a")
minimum = suffix_a[0] # Split before the first character.
prefix_b = 0
for split in range(1, n + 1): # O(n) time to scan all split points.
if s[split - 1] == "b":
prefix_b += 1
minimum = min(minimum, prefix_b + suffix_a[split])
return minimum
C++
#ifndef LEETCODE_MINIMUMDELETIONSTOMAKESTRINGBALANCED_HPP
#define LEETCODE_MINIMUMDELETIONSTOMAKESTRINGBALANCED_HPP
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution1653 {
public:
// O(n) time; O(1) extra space. Keep the best result for each prefix.
int minimumDeletions(const string &s) {
int bCount = 0;
int deletions = 0;
for (char c : s) {
if (c == 'b') {
bCount++;
} else {
// Delete this 'a', or delete all earlier 'b's.
deletions = min(deletions + 1, bCount);
}
}
return deletions;
}
// O(n) time; O(n) extra space for suffix counts of 'a'.
int minimumDeletionsBySplit(const string &s) {
const int n = static_cast<int>(s.size());
vector<int> suffixA(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
suffixA[i] = suffixA[i + 1] + (s[i] == 'a');
}
int prefixB = 0;
int minimum = n;
for (int split = 0; split <= n; split++) {
// Keep 'b's before the split and 'a's after it.
minimum = min(minimum, prefixB + suffixA[split]);
if (split < n && s[split] == 'b') {
prefixB++;
}
}
return minimum;
}
};
#endif // LEETCODE_MINIMUMDELETIONSTOMAKESTRINGBALANCED_HPP
Rust
pub struct Solution;
impl Solution {
/// One-pass DP. O(n) time, O(1) extra space.
pub fn minimum_deletions(s: String) -> i32 {
let mut b_count = 0;
let mut deletions = 0;
for &byte in s.as_bytes() {
if byte == b'b' {
b_count += 1;
} else {
// Delete this 'a', or delete every earlier 'b'.
deletions = (deletions + 1).min(b_count);
}
}
deletions
}
/// Check every split using suffix 'a' counts. O(n) time, O(n) extra space.
pub fn minimum_deletions_by_split(s: String) -> i32 {
let bytes = s.as_bytes();
let n = bytes.len();
let mut suffix_a = vec![0; n + 1];
for i in (0..n).rev() {
suffix_a[i] = suffix_a[i + 1] + i32::from(bytes[i] == b'a');
}
let mut prefix_b = 0;
let mut minimum = n as i32;
for split in 0..=n {
minimum = minimum.min(prefix_b + suffix_a[split]);
if split < n && bytes[split] == b'b' {
prefix_b += 1;
}
}
minimum
}
}