# 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 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.

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.

• 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;
}
}

• 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;
}
};

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


• 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
}

• 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;
}