Skip to content

3223. Minimum Length of String After Operations

Description

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 occurrence of s[i] located to the left of i.
  • Delete the closest occurrence of s[i] located to the right of i.

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

 

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 * 105
  • s consists only of lowercase English letters.

Solutions

Solution 1: Counting

We can count the occurrences of each character in the string, and then iterate through the count array. If a character appears an odd number of times, then \(1\) of that character remains in the end; if a character appears an even number of times, then \(2\) of that character remain. We can sum the remaining counts of all characters to get the final length of the string.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(|\Sigma|)\), where \(|\Sigma|\) is the size of the character set, which is \(26\) in this problem.

1
2
3
4
class Solution:
    def minimumLength(self, s: str) -> int:
        cnt = Counter(s)
        return sum(1 if x & 1 else 2 for x in cnt.values())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minimumLength(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        int ans = 0;
        for (int x : cnt) {
            if (x > 0) {
                ans += x % 2 == 1 ? 1 : 2;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumLength(string s) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        int ans = 0;
        for (int x : cnt) {
            if (x) {
                ans += x % 2 ? 1 : 2;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func minimumLength(s string) (ans int) {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    for _, x := range cnt {
        if x > 0 {
            if x&1 == 1 {
                ans += 1
            } else {
                ans += 2
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minimumLength(s: string): number {
    const cnt = new Map<string, number>();
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    let ans = 0;
    for (const x of cnt.values()) {
        ans += x & 1 ? 1 : 2;
    }
    return ans;
}

Comments