Minimum Length of String After Operations - Solution & Explanation
Problem Statement
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 Overview
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.
Approach 1: Two-pointer Technique
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.
Complexity
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.
Approach 2: Stack-based Reduction
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.
Complexity
Time Complexity: O(n), Space Complexity: O(n).
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Length of String After Operations | 2 Approaches |Intuition |Leetcode 3223 |codestorywithMIK • codestorywithMIK • 7,084 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Length of String After Operations easy or hard?
Minimum Length of String After Operations Python/Java solution
How to solve Minimum Length of String After Operations in O(n)?
What is the best approach for Minimum Length of String After Operations?
Is Minimum Length of String After Operations asked at Google/Amazon/Meta?
What data structure is used in Minimum Length of String After Operations?
What is the time complexity of Minimum Length of String After Operations?
Ready to solve this problem?
Practice Minimum Length of String After Operations with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor