Watch 10 video solutions for Minimum Length of String After Operations, a medium level problem involving Hash Table, String, Counting. This walkthrough by codestorywithMIK has 6,929 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |