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.Problem Overview: You are given a string and allowed to perform operations that remove pairs of equal characters under specific conditions. After applying any number of valid operations, the goal is to determine the smallest possible length of the remaining string.
Approach 1: Stack-based Reduction (O(n) time, O(n) space)
This approach simulates the removal process directly. Iterate through the string and push characters onto a stack. When the current character forms a removable pattern with characters already on the stack, pop the matching elements to simulate the operation. The stack always represents the current reduced string after processing each character. Because each character is pushed and popped at most once, the total time complexity is O(n) and the auxiliary space is O(n). This method is useful when you want to model the operations exactly as described and visualize how reductions occur.
Approach 2: Two-pointer Technique with Frequency Counting (O(n) time, O(1) space)
A more optimal insight comes from observing that operations only reduce the frequency of characters in pairs. Instead of simulating every removal, count how many times each character appears using a hash table or fixed-size array for lowercase letters. For each character, repeatedly removing valid pairs leaves at most one or two occurrences depending on the count parity. Summing these remaining counts gives the final minimum length. This method scans the string once to compute frequencies and once to aggregate the result, resulting in O(n) time and O(1) extra space since the alphabet size is constant.
The key insight is that the order of operations does not affect the final count of characters that cannot be paired away. Once you know the frequency of each letter, you can determine how many characters must remain without simulating every operation. This converts what looks like a repeated string manipulation problem into a simple counting problem using a hash table or frequency array.
Recommended for interviews: Start by explaining the stack simulation because it mirrors the operation rules and shows clear reasoning about the process. Then present the optimized counting approach using counting and string analysis. Interviewers typically expect the O(n) counting solution since it avoids unnecessary simulation while still being easy to reason about.
The idea is to use two pointers, start from both ends and move towards the center to find possible deletions. By tracking pairs of identical characters, we can optimally remove pairs until no more operations are possible.
This solution uses a two-pointer approach to check both ends of the string s. It increments the left pointer and decrements the right pointer if the characters at these positions are equal, effectively tracking and removing the mirrored characters towards the center.
Time Complexity: O(n), where n is the length of the string, as each element is checked at most once. Space Complexity: O(1), as no additional data structures are used.
Instead of using the two-pointer method, this approach uses a stack to help determine operations. As we iterate through the string, we identify characters that can be removed based on previous ones and reduce the string progressively.
In this C solution, a stack is used to evaluate and track removable characters while iterating through the string. The stack helps manage operations like collapsing character pairs efficiently.
Time Complexity: O(n), Space Complexity: O(n).
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-pointer Technique | Time Complexity: O(n), where n is the length of the string, as each element is checked at most once. Space Complexity: O(1), as no additional data structures are used. |
| Stack-based Reduction | Time Complexity: O(n), Space Complexity: O(n). |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Reduction | O(n) | O(n) | When you want to simulate the operations exactly as described and track reductions step by step |
| Two-pointer + Frequency Counting | O(n) | O(1) | Best general solution when only the final minimal length matters |
Minimum Length of String After Operations | 2 Approaches |Intuition |Leetcode 3223 |codestorywithMIK • codestorywithMIK • 6,929 views views
Watch 9 more video solutions →Practice Minimum Length of String After Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor