Lexicographically Minimum String After Removing Stars
MedPrompt
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:
- Delete the leftmost
'*'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 <= 105sconsists only of lowercase English letters and'*'.- The input is generated such that it is possible to delete all
'*'characters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly finds the leftmost star, identifies the character to be removed based on the greedy strategy, and reconstructs the string. This process continues until no stars are left.
Algorithm
- Convert the input string
sto a mutableStringBuilder. - Loop as long as a
'*'character exists in theStringBuilder.- Find the index of the leftmost
'*'. Let this bestarIndex. - If no star is found, exit the loop.
- Find the smallest character in the substring to the left of the star (
0tostarIndex - 1). - Find the rightmost index (
removeIndex) of this smallest character in the same left-side substring. - Delete the character at
starIndexfirst, then the character atremoveIndex.
- Find the index of the leftmost
- Convert the
StringBuilderback to a string and return it.
Walkthrough
In this brute-force method, we use a mutable string representation, like Java's StringBuilder, to allow for efficient character deletions. We enter a loop that continues as long as there are '*' characters in the string. In each iteration, we locate the first '*'. Then, we scan all characters to its left to determine the smallest character. To get the lexicographically smallest final string, we must remove the rightmost occurrence of this smallest character. So, we perform a reverse scan from the star's position to find its index. Finally, we delete both the star and the identified character. This is repeated until all stars are processed.
class Solution { public String clearStars(String s) { StringBuilder sb = new StringBuilder(s); while (true) { int starIndex = sb.indexOf("*"); if (starIndex == -1) { break; } char smallestChar = Character.MAX_VALUE; int removeIndex = -1; // Find the smallest character to the left of the star for (int i = 0; i < starIndex; i++) { if (sb.charAt(i) != '*') { smallestChar = (char) Math.min(smallestChar, sb.charAt(i)); } } // Find the rightmost occurrence of that smallest character for (int i = starIndex - 1; i >= 0; i--) { if (sb.charAt(i) == smallestChar) { removeIndex = i; break; } } // Delete star first (larger index) to not affect smaller index sb.deleteCharAt(starIndex); if (removeIndex != -1) { sb.deleteCharAt(removeIndex); } } return sb.toString(); }}Complexity
Time
O(N^2), where N is the length of the string. In each of the O(N) iterations (one for each star), finding the star, the smallest character, and its position takes O(N) time. Deletion in a `StringBuilder` also takes O(N).
Space
O(N), where N is the length of the string, for storing the `StringBuilder`.
Trade-offs
Pros
Conceptually simple and easy to follow the problem's description.
Cons
Highly inefficient due to repeated scanning and modification of the string.
Will likely result in a 'Time Limit Exceeded' error for large inputs.
A more optimized approach is to process the string in a single pass. We can use a Priority Queue to efficiently keep track of the available characters to the left of the current position. The priority queue will be ordered to quickly retrieve the smallest character that appeared most recently (rightmost).
Algorithm
- Create a
PriorityQueueto store pairs of(character, index). - The priority queue's comparator will prioritize smaller characters, and for ties, larger indices.
- Create a boolean array
removedof the same size as the input string, initialized tofalse. - Iterate through the input string
swith indexi:- If
s[i]is a letter, add(s[i], i)to the priority queue. - If
s[i]is a'*', remove the top element from the priority queue and mark its index in theremovedarray astrue.
- If
- After the first pass, build the result string by appending characters
s[i]wheres[i]is not'*'andremoved[i]isfalse.
Walkthrough
The core idea is that for any '*', we must remove the smallest character seen so far. To make the resulting string lexicographically smallest, we should remove the rightmost occurrence of that smallest character. A Priority Queue storing pairs of (character, index) is perfect for this. We customize its comparator to sort first by character ('a' before 'b') and then by index in descending order (rightmost first).
We iterate through the string. When we see a letter, we add a (character, index) pair to the priority queue. When we see a '*', we poll() from the queue. This gives us the smallest character with its largest index, which is exactly the character we need to remove. We don't modify the string in-place; instead, we mark its original index as 'removed' in a boolean array. After this single pass, we construct the final string by iterating through the original string and appending only the characters that are not stars and not marked as removed.
import java.util.PriorityQueue; class Solution { public String clearStars(String s) { class Pair { char c; int index; Pair(char c, int index) { this.c = c; this.index = index; } } PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> { if (a.c != b.c) { return a.c - b.c; } return b.index - a.index; // Larger index first for ties }); boolean[] removed = new boolean[s.length()]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '*') { if (!pq.isEmpty()) { Pair toRemove = pq.poll(); removed[toRemove.index] = true; } } else { pq.add(new Pair(c, i)); } } StringBuilder result = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != '*' && !removed[i]) { result.append(s.charAt(i)); } } return result.toString(); }}Complexity
Time
O(N log N). Each of the N characters is processed. For letters, we add to the PQ (O(log K) where K is PQ size). For stars, we remove from the PQ (O(log K)). In the worst case, K can be O(N), leading to O(N log N) overall.
Space
O(N). The Priority Queue can store up to N elements in the worst case (a string with no stars). The `removed` array also takes O(N) space.
Trade-offs
Pros
Much faster than the naive approach, passing typical constraints.
Processes the string in a single pass to determine removals.
Cons
Slower than the optimal linear time solution due to the logarithmic time complexity of priority queue operations.
This is the most efficient approach, achieving linear time complexity. It improves upon the priority queue by using a more specialized data structure: an array of lists (or stacks), one for each character of the alphabet. This allows finding the smallest available character in constant time.
Algorithm
- Create an array of 26 lists,
positions, to store indices for each character 'a' through 'z'. - Create a boolean array
removedof sizes.length(), initialized tofalse. - Iterate through the input string
swith indexi:- If
s[i]is a letterc, addito the listpositions[c-'a']. - If
s[i]is a'*', find the smallestjfrom 0 to 25 such thatpositions[j]is not empty.- Remove the last index from
positions[j](this is the rightmost occurrence). - Mark this index as
truein theremovedarray. - Break the inner loop and continue to the next character of
s.
- Remove the last index from
- If
- Build the final result string by appending characters
s[i]wheres[i]is not'*'andremoved[i]isfalse.
Walkthrough
Instead of a generic priority queue, we can use an array of 26 lists, where positions[c-'a'] stores the indices of all occurrences of character c seen so far. We iterate through the input string s. If s[i] is a letter, we add its index i to the corresponding list. Since we add indices in increasing order, the last element in any list is always the index of the rightmost occurrence of that character.
If s[i] is a '*', we find the smallest character available for removal. We do this by iterating through our positions array from index 0 ('a') to 25 ('z'). The first non-empty list corresponds to the smallest character. We then pop the last index from this list and mark it for deletion in a removed boolean array. This check for the smallest character takes at most 26 steps, which is a constant time operation.
After this single pass, we construct the final string by collecting all characters from s that are not stars and not marked as removed.
import java.util.ArrayList;import java.util.List; class Solution { public String clearStars(String s) { List<List<Integer>> positions = new ArrayList<>(); for (int i = 0; i < 26; i++) { positions.add(new ArrayList<>()); } boolean[] removed = new boolean[s.length()]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '*') { for (int j = 0; j < 26; j++) { // Find smallest char if (!positions.get(j).isEmpty()) { List<Integer> indices = positions.get(j); int indexToRemove = indices.remove(indices.size() - 1); removed[indexToRemove] = true; break; } } } else { positions.get(c - 'a').add(i); } } StringBuilder result = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != '*' && !removed[i]) { result.append(s.charAt(i)); } } return result.toString(); }}Complexity
Time
O(N). The main loop runs N times. Inside the loop, for letters, it's an O(1) append to a list. For stars, we search for the smallest character, which takes at most 26 steps (a constant, so O(1)). All other operations are O(1). The final string construction is O(N).
Space
O(N). The `positions` data structure can store up to N indices in total across all lists. The `removed` array also requires O(N) space.
Trade-offs
Pros
Optimal O(N) time complexity.
Efficiently implements the greedy strategy in a single pass.
Cons
Slightly more complex to implement than the priority queue approach due to managing the array of lists.
Solutions
Solution
public class Solution { public string ClearStars(string s) { int n = s.Length; List < int > [] g = new List < int > [26]; for (int i = 0; i < 26; i++) { g[i] = new List < int > (); } bool[] rem = new bool[n]; for (int i = 0; i < n; i++) { char ch = s[i]; if (ch == '*') { rem[i] = true; for (int j = 0; j < 26; j++) { if (g[j].Count > 0) { int idx = g[j][g[j].Count - 1]; g[j].RemoveAt(g[j].Count - 1); rem[idx] = true; break; } } } else { g[ch - 'a'].Add(i); } } var ans = new System.Text.StringBuilder(); for (int i = 0; i < n; i++) { if (!rem[i]) { ans.Append(s[i]); } } return ans.ToString(); }}class Solution {public String clearStars(String s) { Deque<Integer>[] g = new Deque[26]; Arrays.setAll(g, k->new ArrayDeque<>()); int n = s.length(); boolean[] rem = new boolean[n]; for (int i = 0; i < n; ++i) { if (s.charAt(i) == '*') { rem[i] = true; for (int j = 0; j < 26; ++j) { if (!g[j].isEmpty()) { rem[g[j].pop()] = true; break; } } } else { g[s.charAt(i) - 'a'].push(i); } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; ++i) { if (!rem[i]) { sb.append(s.charAt(i)); } } return sb.toString(); }}class Solution {public: string clearStars(string s) { stack<int> g[26]; int n = s.length(); vector<bool> rem(n); for (int i = 0; i < n; ++i) { if (s[i] == '*') { rem[i] = true; for (int j = 0; j < 26; ++j) { if (!g[j].empty()) { rem[g[j].top()] = true; g[j].pop(); break; } } } else { g[s[i] - 'a'].push(i); } } string ans; for (int i = 0; i < n; ++i) { if (!rem[i]) { ans.push_back(s[i]); } } return ans; }};class Solution: def clearStars(self, s: str) -> str: g = defaultdict(list) n = len(s) rem = [False] * n for i, c in enumerate(s): if c == "*": rem[i] = True for a in ascii_lowercase: if g[a]: rem[g[a]. pop()] = True break else: g[c]. append(i) return "" . join(c for i, c in enumerate(s) if not rem[i])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.