Lexicographically Minimum String After Removing Stars

Lexicographically Minimum String After Removing Stars - Problem

Hash Table String Stack Greedy Heap (Priority Queue) Medium

You are given a string s that may contain any number of '*' characters. Your task is to remove all '*' characters through a specific process.

While there is a '*' in the string, perform the following operation:

Delete the leftmost '*' character
Delete the smallest non-'*' character to its left
If there are several smallest characters, you can delete any of them

Return the lexicographically smallest resulting string after removing all '*' characters.

Input & Output

Example 1 — Basic Case

$ Input: s = "leet*cod*e"

› Output: "lecoe"

💡 Note: First '*' removes 'e' (smallest among 'l','e','e','t'), leaving "let*cod*e". Next '*' removes 'd' (smallest among 'l','e','t','c','o','d'), giving final result "lecoe".

Example 2 — Multiple Same Characters

$ Input: s = "erase*****"

› Output: ""

💡 Note: Each '*' removes the smallest available character: first removes 'a', then 'e', then 'e', then 'r', finally 's', leaving empty string.

Example 3 — No Stars

$ Input: s = "hello"

› Output: "hello"

💡 Note: No '*' characters to process, so the original string is returned unchanged.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters and '*' characters
It is guaranteed that all '*' operations can be applied

Visualization

Tap to expand

Understanding the Visualization

Input String

Original string with stars and characters

Process Stars

Remove stars and smallest characters

Final Result

Lexicographically smallest remaining string

Key Takeaway

🎯 Key Insight: Use a stack to efficiently track characters and greedily remove the smallest character when encountering each '*'

Asked in

G Google 23 a Amazon 18 f Meta 15 m Microsoft 12

The key insight is to process characters left to right using a stack, and when encountering a '*', remove the lexicographically smallest character from the stack. The greedy stack approach works optimally by removing the rightmost occurrence of the smallest character to ensure lexicographically minimum result. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n²)	O(n)	Use stack to efficiently track and remove smallest characters
Brute Force - Direct Simulation	O(n³)	O(n)	Repeatedly find leftmost '*' and remove it with smallest character to its left
Greedy with Smart Stack Management	O(n²)	O(n)	Use stack with frequency counting for optimal character removal

Stack-Based Approach — Algorithm Steps

Process characters left to right
If character is '*', find and remove smallest from stack
Otherwise, add character to stack
Return final stack as string

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Stack

Add non-star characters to stack

Process Star

Find minimum in stack when encountering '*'

Remove Min

Remove smallest character from stack

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int len = strlen(s);
    char* stack = malloc((len + 1) * sizeof(char));
    int stackSize = 0;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '*') {
            if (stackSize > 0) {
                // Find and remove the smallest character
                char minChar = stack[0];
                int minIdx = 0;
                for (int j = 1; j < stackSize; j++) {
                    if (stack[j] < minChar) {
                        minChar = stack[j];
                        minIdx = j;
                    }
                }
                // Remove character at minIdx
                for (int j = minIdx; j < stackSize - 1; j++) {
                    stack[j] = stack[j + 1];
                }
                stackSize--;
            }
        } else {
            stack[stackSize++] = s[i];
        }
    }
    
    stack[stackSize] = '\0';
    return stack;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each star, we scan the stack of up to n characters to find minimum

⚠ Quadratic Growth

Space Complexity

O(n)

Stack stores up to n characters

⚡ Linearithmic Space

23.6K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler