Skip to content

3746. Minimum String Length After Balanced Removals

Description

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

You are allowed to repeatedly remove any substring where the number of 'a' characters is equal to the number of 'b' characters. After each removal, the remaining parts of the string are concatenated together without gaps.

Return an integer denoting the minimum possible length of the string after performing any number of such operations.

 

Example 1:

Input: s = "aabbab"

Output: 0

Explanation:

The substring "aabbab" has three 'a' and three 'b'. Since their counts are equal, we can remove the entire string directly. The minimum length is 0.

Example 2:

Input: s = "aaaa"

Output: 4

Explanation:

Every substring of "aaaa" contains only 'a' characters. No substring can be removed as a result, so the minimum length remains 4.

Example 3:

Input: s = "aaabb"

Output: 1

Explanation:

First, remove the substring "ab", leaving "aab". Next, remove the new substring "ab", leaving "a". No further removals are possible, so the minimum length is 1.

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either 'a' or 'b'.

Solutions

Solution 1: Counting

According to the problem description, as long as adjacent characters are different, we can remove them. Therefore, the final remaining string will only contain the same character, either all 'a' or all 'b'. So we only need to count the number of 'a' and 'b' in the string, and the final minimum length is the absolute difference between their counts.

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

1
2
3
4
5
class Solution:
    def minLengthAfterRemovals(self, s: str) -> int:
        a = s.count("a")
        b = len(s) - a
        return abs(a - b)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minLengthAfterRemovals(String s) {
        int n = s.length();
        int a = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == 'a') {
                ++a;
            }
        }
        int b = n - a;
        return Math.abs(a - b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minLengthAfterRemovals(string s) {
        int a = 0;
        for (char c : s) {
            if (c == 'a') {
                ++a;
            }
        }
        int b = s.size() - a;
        return abs(a - b);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minLengthAfterRemovals(s string) int {
    a := strings.Count(s, "a")
    b := len(s) - a
    return abs(a - b)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function minLengthAfterRemovals(s: string): number {
    let a = 0;
    for (const c of s) {
        if (c === 'a') {
            ++a;
        }
    }
    const b = s.length - a;
    return Math.abs(a - b);
}

Comments