Lexicographically Minimum String After Removing Stars Solution
Lexicographically Minimum String After Removing Stars solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Lexicographically Minimum String After Removing Stars is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack, Heap
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
s contains lowercase letters and '*' characters. While a '*' remains, you must:
- delete the smallest non-star character anywhere to its left, and
- delete that
'*'itself.
When several characters tie for smallest you may delete any one of them. Return the lexicographically smallest string that can remain.
Example 1
Input: s = "codekairo*"
Output: codekiro
Explanation: The smallest letter to the left of the star is `a`.
Example 2
Input: s = "aaba*"
Output: aab
Explanation: Among the three `a`s, deleting the **rightmost** leaves `aab`, which beats `aba`.
Example 3
Input: s = "abc"
Output: abc
Explanation: No stars, nothing to remove.
Constraints
1 <= s.length <= 10^5s consists only of lowercase English letters and '*'.The input is generated such that the operation is always possible.
Hints for Lexicographically Minimum String After Removing Stars
Hint 1
You have no choice about which letter value is deleted — always the smallest available. The freedom is only in which occurrence of it.
Hint 2
Among equal smallest letters, deleting the rightmost occurrence is best: it keeps the earlier copies, which push smaller characters further left.
Hint 3
Keep one stack of indices per letter; a star pops the top of the lowest non-empty stack.
How to solve Lexicographically Minimum String After Removing Stars
Maintain 26 stacks of positions, one per letter. Every letter pushes its index onto its stack; every star pops the top index of the lowest non-empty stack and marks both positions deleted. A final pass emits the survivors in their original order.
Approach
- For each character: a letter pushes its index onto
stacks[c - 'a']. - A star marks itself deleted, then scans letters
aupward for the first non-empty stack and marks its top index deleted. - Build the answer from the unmarked positions, left to right.
Why it works
Using a stack rather than a queue is the whole trick. The smallest letter is forced, but among equal copies removing the rightmost is optimal: deleting an earlier copy would shift a later, larger character into an earlier position, and the first position where two candidate answers differ is what decides the comparison. Scanning 26 stacks per star keeps each operation O(26) — a priority queue of (letter, index) pairs is the same idea at O(log n).
Complexity
- Time —
O(26 · n) - Space —
O(n)
Pitfalls
- Deleting the leftmost copy of the smallest letter gives a larger string — the stack direction matters.
- The star itself is deleted as well as the letter it consumes.
- The surviving characters keep their original relative order; nothing is sorted.
Reference solution
Python
def clearStars(s: str) -> str:
stacks = [[] for _ in range(26)]
removed = [False] * len(s)
for i, c in enumerate(s):
if c == "*":
removed[i] = True
for k in range(26):
if stacks[k]:
removed[stacks[k].pop()] = True
break
else:
stacks[ord(c) - 97].append(i)
return "".join(s[i] for i in range(len(s)) if not removed[i])Java
public static String clearStars(String s) {
List<List<Integer>> stacks = new ArrayList<>();
for (int i = 0; i < 26; i++) stacks.add(new ArrayList<>());
boolean[] removed = new boolean[s.length()];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '*') {
removed[i] = true;
for (int k = 0; k < 26; k++) {
List<Integer> st = stacks.get(k);
if (!st.isEmpty()) {
removed[st.remove(st.size() - 1)] = true;
break;
}
}
} else {
stacks.get(c - 'a').add(i);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!removed[i]) sb.append(s.charAt(i));
}
return sb.toString();
}C++
string clearStars(string s) {
vector<vector<int>> stacks(26);
vector<bool> removed(s.size(), false);
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] == '*') {
removed[i] = true;
for (int k = 0; k < 26; k++) {
if (!stacks[k].empty()) {
removed[stacks[k].back()] = true;
stacks[k].pop_back();
break;
}
}
} else {
stacks[s[i] - 'a'].push_back(i);
}
}
string out;
for (int i = 0; i < (int) s.size(); i++) {
if (!removed[i]) out += s[i];
}
return out;
}JavaScript
var clearStars = function(s) {
var stacks = [], i, k;
for (i = 0; i < 26; i++) stacks.push([]);
var removed = [];
for (i = 0; i < s.length; i++) removed.push(false);
for (i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (c === "*") {
removed[i] = true;
for (k = 0; k < 26; k++) {
if (stacks[k].length > 0) {
removed[stacks[k].pop()] = true;
break;
}
}
} else {
stacks[s.charCodeAt(i) - 97].push(i);
}
}
var out = "";
for (i = 0; i < s.length; i++) if (!removed[i]) out += s.charAt(i);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms