You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.
While there is a '*', do the following operation:
'*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.Return the lexicographically smallest resulting string after removing all '*' characters.
Example 1:
Input: s = "aaba*"
Output: "aab"
Explanation:
We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.
Example 2:
Input: s = "abc"
Output: "abc"
Explanation:
There is no '*' in the string.
Constraints:
1 <= s.length <= 105s consists only of lowercase English letters and '*'.'*' characters.Problem Overview: You receive a string containing lowercase letters and *. Each star deletes itself and one character to its left. When multiple characters exist to the left, remove the lexicographically smallest one so the final string becomes as small as possible.
Approach 1: Stack to Track Before Deletions (O(n log n) time, O(n) space)
Scan the string from left to right while tracking characters that appear before each *. Maintain a stack (or indexed storage) of characters along with their positions, and use a min‑heap or ordered structure to quickly locate the smallest available character. When you encounter a star, pop the lexicographically smallest character that appears before it and mark both the star and that character for deletion. Continue scanning until the end, then rebuild the string using only characters not removed. The key idea is greedy removal: deleting the smallest possible character before every star guarantees the remaining prefix stays lexicographically minimal. This technique commonly combines stack tracking with a heap (priority queue) to efficiently select the best character to delete.
Approach 2: Two Pointers Technique (O(n) time, O(n) space)
A more optimized method processes the string while maintaining candidate positions for each character. Instead of repeatedly searching, track indices of characters using fixed buckets (for example, 26 lists for each letter). Move through the string with a pointer and record the positions of characters you see. When a * appears, identify the smallest available letter bucket that still has a valid index and remove the most recent occurrence of that letter. This effectively simulates deletions without expensive heap operations. After processing the entire string, reconstruct the result by skipping removed indices. Because each character is inserted and removed at most once, the algorithm runs in linear time. The logic relies on greedy selection and efficient character tracking, a common pattern in string and greedy problems.
Recommended for interviews: The linear two‑pointer/bucket strategy is usually what interviewers expect. It demonstrates that you understand the greedy requirement and can optimize away repeated searches. Starting with the stack + heap idea is still valuable because it clearly models the rule "remove the smallest character before each star" and shows the reasoning before optimizing to O(n).
This approach utilizes a stack data structure to keep track of characters in the string. As we iterate through the string, we push non-'*' characters onto the stack. When we encounter a '*', we pop from the stack, effectively removing the smallest character before the '*'. The stack allows us to maintain the remaining string in a way that can efficiently remove and process characters in a LIFO manner. Finally, we assemble our result from the characters remaining in the stack, which ensures the string is the lexicographically smallest possible after all required deletions.
The C code uses a dynamic character array as a stack to store non-'*' characters. As it iterates through the input string, it pushes characters onto the stack, and pops the stack when a '*' is encountered. The final stack content forms the result.
Time Complexity: O(n) where n is the length of the string, as each character is pushed and popped at most once.
Space Complexity: O(n) due to the usage of a stack to store characters.
This approach leverages two pointers: one pointing to the current position in the input and another building the result in place. The fundamental idea is to overwrite the unnecessary characters in the array as we build the result string. We use the second pointer to track the last added character when we encounter a '*' and need to delete. After iterating through the entire input, the section of the array up to the second pointer will hold the resulting string.
This C code utilizes two pointers within the same array to process the characters. One advances through the input while the second adjusts the positions of meaningful characters, ensuring in-place modification of the string.
Time Complexity: O(n) because every character is processed.
Space Complexity: O(1) as we modify the input in place.
We define an array g to record the index list of each character, and a boolean array rem of length n to record whether each character needs to be deleted.
We traverse the string s:
If the current character is an asterisk, we need to delete it, so we mark rem[i] as deleted. At the same time, we need to delete the character with the smallest lexicographical order and the largest index at this time. We traverse the 26 lowercase letters in ascending order. If g[a] is not empty, we delete the last index in g[a] and set the corresponding index in rem as deleted.
If the current character is not an asterisk, we add the index of the current character to g.
Finally, we traverse s and concatenate the undeleted characters.
The time complexity is O(n times |\Sigma|), and the space complexity is O(n). Where n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
| Approach | Complexity |
|---|---|
| Using Stack to Track Before Deletions | Time Complexity: O(n) where n is the length of the string, as each character is pushed and popped at most once. |
| Two Pointers Technique | Time Complexity: O(n) because every character is processed. |
| Record Indices by Character | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack + Priority Queue | O(n log n) | O(n) | Straightforward greedy simulation when you want a clear mapping between stars and removed characters |
| Two Pointers / Character Buckets | O(n) | O(n) | Optimal solution for interviews and large inputs; avoids heap operations |
Lexicographically Minimum String After Removing Stars | Easy | Leetcode 3170 | codestorywithMIK • codestorywithMIK • 11,346 views views
Watch 9 more video solutions →Practice Lexicographically Minimum String After Removing Stars with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor