Lexicographically Minimum String After Removing Stars — Medium Problem & Solution

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^5
• s consists only of lowercase English letters and '*'.
• The input is generated such that the operation is always possible.

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

1. For each character: a letter pushes its index onto stacks[c - 'a'].
2. A star marks itself deleted, then scans letters a upward for the first non-empty stack and marks its top index deleted.
3. 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])

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium