Skip to content

1653. Minimum Deletions to Make String Balanced

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @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];
};

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

1
2
3
4
5
6
7
8
9
class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = b = 0
        for c in s:
            if c == 'b':
                b += 1
            else:
                ans = min(ans + 1, b)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int ans = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'b') {
                ++b;
            } else {
                ans = Math.min(ans + 1, b);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minimumDeletions(string s) {
        int ans = 0, b = 0;
        for (char& c : s) {
            if (c == 'b') {
                ++b;
            } else {
                ans = min(ans + 1, b);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minimumDeletions(s string) int {
    ans, b := 0, 0
    for _, c := range s {
        if c == 'b' {
            b++
        } else {
            ans = min(ans+1, b)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minimumDeletions(s: string): number {
    let [ans, b] = [0, 0];

    for (const ch of s) {
        if (ch === 'b') {
            ++b;
        } else {
            ans = Math.min(ans + 1, b);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @return {number}
 */
var minimumDeletions = function (s) {
    let [ans, b] = [0, 0];

    for (const ch of s) {
        if (ch === 'b') {
            ++b;
        } else {
            ans = Math.min(ans + 1, b);
        }
    }
    return ans;
};

Solution 3: Two-Variable Method

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minimumDeletions(s: string): number {
    let ra = [...s].reduce((acc, x) => (x === 'a' ? acc + 1 : acc), 0);
    let lb = 0;

    let ans = s.length;
    for (const ch of s) {
        if (ch === 'a') ra--;
        ans = Math.min(ans, lb + ra);
        if (ch === 'b') lb++;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @return {number}
 */
var minimumDeletions = function (s) {
    let ra = [...s].reduce((acc, x) => (x === 'a' ? acc + 1 : acc), 0);
    let lb = 0;

    let ans = s.length;
    for (const ch of s) {
        if (ch === 'a') ra--;
        ans = Math.min(ans, lb + ra);
        if (ch === 'b') lb++;
    }
    return ans;
};

Solution 4: Stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minimumDeletions(s: string): number {
    const stk: string[] = [];
    let res = 0;

    for (const ch of s) {
        if (stk.at(-1) === 'b' && ch === 'a') {
            stk.pop();
            res++;
        } else stk.push(ch);
    }

    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @return {number}
 */
var minimumDeletions = function (s) {
    const stk = [];
    let res = 0;

    for (const ch of s) {
        if (stk.at(-1) === 'b' && ch === 'a') {
            stk.pop();
            res++;
        } else stk.push(ch);
    }

    return res;
};

Comments