Welcome to Subscribe On Youtube
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 indexi
that is equal tos[i]
, and at least one character to the right that is also equal tos[i]
.  Delete the closest character to the left of index
i
that is equal tos[i]
.  Delete the closest character to the right of index
i
that is equal tos[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 * 10^{5}
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; }