You are given a string s.
You can perform the following process on s any number of times:
- Choose an index
iin the string such that there is at least one character to the left of indexithat 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
ithat is equal tos[i]. - Delete the closest character to the right of index
ithat 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 * 105sconsists only of lowercase English letters.
Approach 01:
-
C++
-
Python
class Solution {
public:
int minimumLength(string str) {
unordered_map<char, int> charFrequency;
int length = str.length();
// Count the frequency of each character in the string
for (char &ch : str) {
++charFrequency[ch];
}
// Adjust the length based on character frequencies
for (auto [character, frequency] : charFrequency) {
if (frequency % 2 == 0 && frequency > 2) {
length = length - frequency + 2;
} else if (frequency % 2 != 0 && frequency > 2) {
length = length - frequency + 1;
}
}
return length;
}
};
class Solution:
def minimumLength(self, s: str) -> int:
charFrequency = {}
length = len(s)
# Count the frequency of each character in the string
for ch in s:
charFrequency[ch] = charFrequency.get(ch, 0) + 1
# Adjust the length based on character frequencies
for character, frequency in charFrequency.items():
if frequency % 2 == 0 and frequency > 2:
length = length - frequency + 2
elif frequency % 2 != 0 and frequency > 2:
length = length - frequency + 1
return length
Time Complexity:
- Character Frequency Count:
We iterate through the string once to calculate the frequency of each character, which takes \( O(n) \), where \( n \) is the length of the string.
- Adjusting Length:
We iterate through the unordered map containing character frequencies. In the worst case, there are at most 26 entries (for lowercase English letters), making this step \( O(1) \).
- Overall Time Complexity:
\( O(n) \).
Space Complexity:
- Unordered Map:
The unordered map can store at most 26 entries for lowercase English letters, resulting in \( O(1) \) space usage.
- Additional Variables:
We use a constant amount of space for variables like
lengthand loop iterators. - Overall Space Complexity:
\( O(1) \).