You are given a string s.
Consider performing the following operation until s becomes empty:
'a' to 'z', remove the first occurrence of that character in s (if it exists).For example, let initially s = "aabcbbca". We do the following operations:
s = "aabcbbca". The resulting string is s = "abbca".s = "abbca". The resulting string is s = "ba".s = "ba". The resulting string is s = "".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 * 105s consists only of lowercase English letters.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.
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.
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.
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.
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.
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.
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.
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.
Time Complexity: O(n), where n is the string length.
Space Complexity: O(1), apart from fixed size arrays used.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
3039. Apply Operations to Make String Empty | String | Hash Table | Observation Questions🧐 • Aryan Mittal • 1,660 views views
Watch 8 more video solutions →Practice Apply Operations to Make String Empty with our built-in code editor and test cases.
Practice on FleetCode