#3170

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Lexicographically Minimum String After Removing Stars

Find the lexicographically smallest string by removing stars using stack-based state management and careful character selection.

hash table string stack greedy heap priority queue

Problem Statement

You are given a string s containing lowercase letters and '' characters. Each ' ' indicates that the previous character can be removed. Your task is to perform these removals and return the resulting string that is lexicographically smallest.

Repeatedly process the string by removing the character immediately preceding each '' until no stars remain. Ensure that after each operation, the string remains in the minimal lexicographical order, and return the final string after all ' ' have been removed.

Examples

Example 1

Input: s = "aaba*"

Output: "aab"

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"

There is no '*' in the string.

Constraints

1 <= s.length <= 105
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.

Solution Approach

Use a stack to track characters

Iterate over the string and push each letter onto a stack. When encountering a '*', pop the top of the stack to remove the last character, simulating the required operation.

Maintain lexicographical order

After each removal, the stack contains the partial string. Always ensure that removals consider the smallest possible character to keep the resulting string lexicographically minimal.

Build the final string efficiently

After processing all characters, convert the stack contents to a string. This gives the final lexicographically minimum string without any '*' characters, handling all edge cases efficiently.

Complexity Analysis

Metric	Value
Time	O(n \times
Space	O(n +

Time complexity is O(n * |Σ|) because each character is pushed or popped once and comparisons may involve the alphabet size. Space complexity is O(n + |Σ|) for the stack and hash tables used to track character frequencies or positions.

What Interviewers Usually Probe

Expect candidates to manage stack operations accurately under '*' deletions.
Look for awareness of lexicographical order when deciding which characters to remove.
Check that the solution scales efficiently with large strings up to length 10^5.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly pop the last character for each '*', breaking lexicographical order.
Ignoring edge cases where multiple consecutive '*' appear.
Attempting to sort after all removals instead of maintaining order during processing.

Follow-up variants

Return the lexicographically largest string after removing stars using the same pattern.
Allow additional operations such as replacing letters with '*', still requiring minimal result.
Process strings with Unicode characters, maintaining lexicographical ordering and stack logic.

FAQ

What is the best approach to handle consecutive '*' in this problem?

Using a stack ensures each '*' removes the immediate preceding character, even for multiple consecutive stars, maintaining the correct order.

How do I ensure the result is lexicographically minimal?

Always remove the last character in the current stack when encountering a '*', so the remaining string preserves the smallest order.

Can I solve this without a stack?

A stack is the simplest way to manage state efficiently. Using string concatenation or repeated slicing leads to higher time complexity.

What are the constraints on string length and characters?

The string length is 1 to 10^5, consisting only of lowercase English letters and '', guaranteeing all ' ' can be removed.

How does stack-based state management help in this LeetCode problem?

It tracks the current sequence of letters, allowing immediate removal upon seeing '*', and ensures the resulting string is lexicographically minimal.

terminal

Solution

Solution 1: Record Indices by Character

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#3081 replace question marks in string to minimize its value #2813 maximum elegance of a k length subsequence #2434 using a robot to print the lexicographically smallest string