LeetCode 3170 - Lexicographically Minimum String After Removing Stars

LeetCode Problem 3170

Difficulty: 🟡 Medium
Topics: Hash Table, String, Stack, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to transform a string s that may contain the '*' character into a lexicographically smallest string by repeatedly applying a deletion operation. Specifically, for each '*' in the string, we must remove it along with the smallest non-'*' character to its left. If there are multiple occurrences of the smallest character, any of them can be removed.

The input is a string of lowercase English letters and asterisks with length up to 105. The output is the string that remains after performing the deletion operation for all '*' characters, while ensuring the resulting string is lexicographically minimal. The constraints guarantee that every '*' has at least one character to its left to delete, so we do not need to handle invalid deletions.

Important edge cases include strings with no '*', strings composed entirely of '*', or strings where multiple characters are equally minimal to the left of a '*'. Handling ties correctly and maintaining lexicographic minimality are the key challenges.

Approaches

The brute-force approach is straightforward: for each '*', scan left to find the smallest character and remove it along with the '*'. Repeat until no '*' remain. While correct, this approach requires scanning up to O(n) characters for each '*', resulting in worst-case time complexity of O(n^2) for a string of length n. This is too slow for the input constraints of up to 105 characters.

The optimal approach leverages a stack to simulate the string building process. We iterate through the string from left to right, pushing characters onto the stack. When we encounter a '*', we remove the top element of the stack, which corresponds to the most recently added character and is the correct choice for lexicographic minimality due to the greedy property of the stack. This ensures each '*' deletes the leftmost minimal character efficiently, in O(1) per operation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Scan left for each '*', too slow for large strings
Optimal (Stack)	O(n)	O(n)	Use stack to efficiently track characters to delete

Algorithm Walkthrough

1. Initialize an empty stack to keep track of characters in the string.
2. Iterate over each character c in the string s.
3. If c is not '*', push it onto the stack.
4. If c is '*', pop the top character from the stack. This simulates deleting the '*' and the smallest character to its left.
5. Continue until all characters in the string are processed.
6. Convert the stack back into a string by joining its elements in order.

Why it works: The stack maintains the current valid prefix of the resulting string. Popping from the stack when encountering a '*' ensures we always remove the most recent character that contributes to lexicographic order. The greedy property guarantees that this results in the smallest possible string because every deletion is locally optimal and processed in left-to-right order.

Python Solution

class Solution:
    def clearStars(self, s: str) -> str:
        stack = []
        for c in s:
            if c == '*':
                if stack:
                    stack.pop()
            else:
                stack.append(c)
        return ''.join(stack)

Implementation Explanation: We initialize a stack to simulate the string. Iterating over the input, non-'*' characters are appended to the stack. For each '*', we pop the last element of the stack to remove the leftmost minimal character in context. Finally, joining the stack gives the resulting string.

Go Solution

func clearStars(s string) string {
    stack := []rune{}
    for _, c := range s {
        if c == '*' {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else {
            stack = append(stack, c)
        }
    }
    return string(stack)
}

Go-specific Notes: Go does not have a built-in stack, so we use a slice of rune. Popping is done by slicing off the last element. Converting the slice back to a string is achieved with string(stack). This handles multi-byte characters correctly by using rune instead of byte.

Worked Examples

Example 1: s = "aaba*"

Step	Character	Stack State	Action
1	'a'	['a']	push 'a'
2	'a'	['a','a']	push 'a'
3	'b'	['a','a','b']	push 'b'
4	'a'	['a','a','b','a']	push 'a'
5	'*'	['a','a','b']	pop 'a'
Result	-	['a','a','b']	join stack → "aab"

Example 2: s = "abc"

Step	Character	Stack State	Action
1	'a'	['a']	push 'a'
2	'b'	['a','b']	push 'b'
3	'c'	['a','b','c']	push 'c'
Result	-	['a','b','c']	join stack → "abc"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed or popped at most once
Space	O(n)	Stack stores up to all characters

The linear complexity is achieved because every character is processed once, and popping from the stack occurs in O(1) time. The stack grows proportionally to the number of non-'*' characters.

Test Cases

# Basic examples
assert Solution().clearStars("aaba*") == "aab"  # single star deletes last 'a'
assert Solution().clearStars("abc") == "abc"    # no stars

# Edge cases
assert Solution().clearStars("*") == ""         # only star, nothing to delete
assert Solution().clearStars("a*") == ""        # single letter and star
assert Solution().clearStars("ab*c*") == "a"    # multiple stars

# Long strings
assert Solution().clearStars("abc*def*ghi*") == "abdegh"  # multiple stars interspersed
assert Solution().clearStars("aaaa*****") == ""           # all letters removed by stars

# No letters to delete
assert Solution().clearStars("") == ""        # empty string

Test	Why
"aaba*"	verifies deletion of minimal character with a star
"abc"	no stars, string unchanged
"*"	only star, nothing left to delete
"ab_c_"	multiple stars affect different positions
"aaaa*****"	repeated characters with consecutive stars
""	empty input handled correctly

Edge Cases

1. Consecutive stars at start: A string like "**abc" could appear, but the constraints guarantee that every '*' has a left character to delete. The implementation ensures no errors by checking if the stack is non-empty before popping.

2. Multiple minimal characters: If the left of a '*' has repeated minimal characters, any one can be removed. Using a stack naturally removes the most recently added character, which is correct for lexicographic minimality.

3. Empty resulting string: Strings like "a*" or "aaaa*****" will eventually produce an empty string. Our stack-based solution correctly returns an empty string in this case, avoiding null or undefined results.