Lexicographically Minimum String After Removing Stars

Medium
1025.

Lexicographically Minimum String After Removing Stars

MediumStringGreedyHeap (Priority Queue)StackAmazonGoogleFlipkart

Lexicographically Minimum String After Removing Stars is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Flipkart interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var clearStars = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • s 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

  1. 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.

  2. Hint 2

    Among equal smallest letters, deleting the rightmost occurrence is best: it keeps the earlier copies, which push smaller characters further left.

  3. 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

  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])

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