Problem

You are given a string s.

You can perform the following process on s any number of times:

  • Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
  • Delete the closest character to the left of index i that is equal to s[i].
  • Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

Examples

Example 1:

Input: s = "abaacbcbb"
Output: 5
Explanation:  
We do the following operations:
- Choose index 2, then remove the characters at indices 0 and 3. The resulting string is `s = "bacbcbb"`.
- Choose index 3, then remove the characters at indices 0 and 5. The resulting string is `s = "acbcb"`

Example 2:

Input: s = "aa"
Output: 2
Explanation:
We cannot perform any operations, so we return the length of the original string.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of lowercase English letters.

Solution

Method 1 - Using Frequency Map

This problem requires the repeated removal of characters based on specific conditions to minimize the string’s length. A crucial insight is that the removal process works effectively only when duplicate characters are symmetrically deleted. As a result, the end state of the string comprises only characters that couldn’t be matched on either side of given character.

The solution leverages the frequency of each character to identify these “unremovable” characters:

  • Characters with odd frequencies will always have at least one instance left.
  • Characters with even frequencies can potentially be fully removed in pairs, but the remainder will be 2.

Approach

  1. Count Character Frequencies: Traverse the string s and calculate the frequency of each character using a frequency array.
  2. Determine the Residual Contribution: For each character, examine its frequency:
    • If the frequency is odd, add 1 to the total length (indicating at least one instance remains).
    • If the frequency is even, add 2 to the total length (indicating all characters can be paired and removed).
  3. Return the Total Minimum Length: Sum the contributions of all characters to determine the final length of the string after all possible operations.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    public int minimumLength(String s) {
        int[] freq = new int[26];
        int totalLen = 0;
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        for (int f : freq) {
            if (f == 0) {
                continue;
            }
            if (f % 2 == 0) {
                totalLen += 2;
            } else {
                totalLen += 1;
            }
        }
        return totalLen;
    }
}
Python
class Solution:
    def minimum_length(self, s: str) -> int:
        freq: list[int] = [0] * 26
        total_len: int = 0
        for c in s:
            freq[ord(c) - ord('a')] += 1
        for f in freq:
            if f == 0:
                continue
            total_len += 2 if f % 2 == 0 else 1
        return total_len

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string s. The string is traversed once to compute character frequencies, and then the frequency array is traversed.
  • 🧺 Space complexity: O(1) since the size of the frequency array is fixed (26 for lowercase letters in the English alphabet), which is constant space usage.