Apply Operations to Make String Empty - Solution & Explanation
Problem Statement
You are given a string s.
Consider performing the following operation until s becomes empty:
- For every alphabet character from
'a'to'z', remove the first occurrence of that character ins(if it exists).
For example, let initially s = "aabcbbca". We do the following operations:
- Remove the underlined characters
s = "aabcbbca". The resulting string iss = "abbca". - Remove the underlined characters
s = "abbca". The resulting string iss = "ba". - Remove the underlined characters
s = "ba". The resulting string iss = "".
Return the value of the string s right before applying the last operation. In the example above, answer is "ba".
Example 1:
Input: s = "aabcbbca" Output: "ba" Explanation: Explained in the statement.
Example 2:
Input: s = "abcd" Output: "abcd" Explanation: We do the following operation: - Remove the underlined characters s = "abcd". The resulting string is s = "". The string just before the last operation is "abcd".
Constraints:
1 <= s.length <= 5 * 105sconsists only of lowercase English letters.
Approach Overview
Problem Overview: You repeatedly apply an operation on a string where the first occurrence of every distinct character is removed in a single round. The process continues until the string becomes empty. The task is to return the string that exists right before the final operation removes the remaining characters.
Approach 1: Simulating the Operations with a Queue (O(n) time, O(n) space)
This approach mimics the process exactly as described. Track the indices of each character using a queue-like structure. In every round, remove the earliest occurrence of each character and push remaining positions back for the next round. The simulation continues until no characters remain, while keeping track of the last non-empty state. The idea is straightforward and closely follows the problem statement, which makes it a good starting point during interviews. However, it performs multiple passes over the data, and managing queues for each character increases implementation overhead.
Approach 2: Direct Simulation Using Index and Mark Replacement (O(n) time, O(1) extra space)
Instead of simulating every round, observe the pattern created by the operations. A character that appears k times will survive exactly k rounds before being completely removed. Therefore, the final remaining string consists only of characters whose frequency equals the maximum frequency in the string. Count occurrences using a counting array, determine the maximum frequency, then iterate through the string to identify the last surviving occurrence for those characters. Ordering is determined by their final positions in the original string, which may require a simple sorting step based on index.
The key insight: every operation removes characters layer by layer from the front. Characters with fewer occurrences disappear earlier, while those with the highest frequency survive until the final round. That means the last non-empty string is formed by the last occurrences of the characters with maximum frequency. This transforms the problem from repeated simulation into a single pass frequency analysis using techniques common in hash table and array problems.
Recommended for interviews: Start with the simulation idea to demonstrate understanding of the operations. Then derive the frequency insight that eliminates repeated rounds. Interviewers typically expect the optimized counting-based solution because it reduces the process to a linear scan and clearly explains why only maximum-frequency characters survive.
Approach 1: Simulating the Operations with a Queue
In this approach, we simulate the operations by queuing characters to handle removals simulating the operations.
This mimics going through the alphabet, removing the first occurrence of each letter from 'a' to 'z' until the string becomes empty. The idea is to use a Queue to keep track of order while iterating from 'a' to 'z'.
This C solution maintains an array to record the first occurrence of characters 'a' to 'z'. It then reconstructs the string after removing those first occurrences.
The original string is modified in place until it becomes empty.
Complexity
Time Complexity: O(n * 26) since for each potential letter (at worst 26), we perform operations on each character.
Space Complexity: O(1) as the space used is constant relative to input size.
Approach 2: Direct Simulation Using Index and Mark Replacement
This approach directly simulates the removals by using indices to mark the positions of the first occurrences of each character 'a' to 'z'.
After marking those indices, it passes through the string and skips removal indices, leading to a progressively shorter string.
The C program handles the string step-by-step through index tracking, directly manipulating the string by replacing visited first occurrences and copying back each iteration.
Complexity
Time Complexity: O(n * k), where k is constant 26 and n the length due to character removal repetition.
Space Complexity: O(n), requires temporary space for new string generation.
Approach 3: Character Frequency Count and Decrement
This approach involves using an array to track the frequency of each character in the string. With each iteration, we decrement the count for the first occurrence of each character from 'a' to 'z'. We keep performing this operation until the string becomes empty, and we return the string state just before the last operation.
This C implementation uses a static buffer to manipulate the string and a frequency array to track which characters are removed. The implementation iteratively modifies the string by removing the first occurrence of each alphabet character. Once the string becomes empty, it returns the state of the string right before it was last emptied.
Complexity
Time Complexity: O(n * 26) = O(n), where n is the length of the string.
Space Complexity: O(n) for storing the input and intermediate string.
Approach 4: Optimized Sliding Window Technique
This optimized approach utilizes a sliding window mechanism. Each step, it advances through the string once and collects characters that are candidates for removal in the current operation while maintaining a record of last removals to optimize processing.
This implementation leverages two indices and character removal tracking to simulate successive elimination without repeatedly initializing character maps. A sliding window effects accumulations into a retained intermediate result string.
Complexity
Time Complexity: O(n), where n is the string length.
Space Complexity: O(1), apart from fixed size arrays used.
Approach 5: Hash Table or Array
We use a hash table or array cnt to record the occurrence times of each character in string s, and use another hash table or array last to record the last occurrence position of each character in string s. The maximum occurrence times of characters in string s is denoted as mx.
Then we traverse the string s. If the occurrence times of the current character equals mx and the position of the current character equals the last occurrence position of this character, then we add the current character to the answer.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(|\Sigma|), where n is the length of string s, and \Sigma is the character set. In this problem, \Sigma is the set of lowercase English letters.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulating the Operations with a Queue | Time Complexity: O(n * 26) since for each potential letter (at worst 26), we perform operations on each character. Space Complexity: O(1) as the space used is constant relative to input size. |
| Direct Simulation Using Index and Mark Replacement | Time Complexity: O(n * k), where k is constant 26 and n the length due to character removal repetition. Space Complexity: O(n), requires temporary space for new string generation. |
| Character Frequency Count and Decrement | Time Complexity: O(n * 26) = O(n), where n is the length of the string. |
| Optimized Sliding Window Technique | Time Complexity: O(n), where n is the string length. |
| Hash Table or Array | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulating the Operations with a Queue | O(n) | O(n) | When you want a direct implementation of the described operations or to verify behavior step-by-step |
| Direct Simulation Using Index and Mark Replacement | O(n) | O(1) | Best general solution using frequency counting and last-occurrence tracking |
Video Solution
3039. Apply Operations to Make String Empty | String | Hash Table | Observation Questions🧐 • Aryan Mittal • 1,705 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Apply Operations to Make String Empty easy or hard?
Apply Operations to Make String Empty Python/Java solution
How to solve Apply Operations to Make String Empty in O(n)?
What is the best approach for Apply Operations to Make String Empty?
Is Apply Operations to Make String Empty asked at Google/Amazon/Meta?
What data structure is used in Apply Operations to Make String Empty?
What is the time complexity of Apply Operations to Make String Empty?
Ready to solve this problem?
Practice Apply Operations to Make String Empty with our built-in code editor and test cases.
Practice on FleetCode