You are given a string s.
You can perform the following process on s any number of times:
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].i that is equal to s[i].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:
s = "bacbcbb".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 * 105s consists only of lowercase English letters.To solve #3223 Minimum Length of String After Operations, observe how the allowed operation affects repeated characters. Each operation effectively removes characters in pairs around the same letter, meaning the final result depends only on how many times each character appears in the string.
Instead of simulating operations, use a hash table or frequency array to count occurrences of each character. For a character appearing k times, repeated operations can shrink the group but cannot eliminate it entirely beyond a certain point. If the frequency is odd, the minimum remaining count for that character becomes 1. If the frequency is even, the minimum remaining count becomes 2. Characters that appear once or twice remain unchanged.
Sum the minimal remaining counts for all characters to compute the final string length. This counting-based insight avoids expensive simulations and leads to an efficient linear-time solution.
Time Complexity: O(n) for counting characters. Space Complexity: O(1) since the alphabet size is fixed.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table / Frequency Counting | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Only the frequency of each character matters in finding the final answer.
If a character occurs less than 3 times, we cannot perform any process with it.
Suppose there is a character that occurs at least 3 times in the string, we can repeatedly delete two of these characters until there are at most 2 occurrences left of it.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like #3223 are common in coding interviews because they test pattern recognition and counting techniques. While the exact question may vary, similar string frequency and greedy reduction problems are frequently asked in FAANG-style interviews.
The allowed operations reduce characters in pairs, which means the parity of each character's count becomes important. After applying all possible operations, each character group stabilizes at either one or two remaining characters depending on whether the original count was odd or even.
A hash table or a fixed-size frequency array works best for this problem. It allows you to count how many times each character appears and apply the parity rule to determine the minimal remaining characters.
The optimal approach uses frequency counting with a hash table or fixed-size array. By analyzing how operations affect repeated characters, you can determine the minimum remaining count for each character without simulating the operations. This results in an O(n) time solution.