Removing Stars From a String - Practice Coding Problems

Removing Stars From a String - Problem

You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.

Input & Output

Example 1 — Basic Star Removal

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

› Output: lecoe

💡 Note: Process left to right: 'leet' → stack has [l,e,e,t]. First '*' removes 't' → [l,e,e]. Second '*' removes 'e' → [l,e]. Then 'cod' → [l,e,c,o,d]. Another '*' removes 'd' → [l,e,c,o]. Finally 'e' → [l,e,c,o,e] = "lecoe"

Example 2 — All Characters Removed

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

› Output: ""

💡 Note: Start with 'erase' in stack. Five stars remove all five characters one by one, leaving empty string

Example 3 — No Stars

$ Input: s = "hello"

› Output: hello

💡 Note: No stars present, so all characters remain: 'hello'

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters and stars *
The operation is always possible (guaranteed by problem)

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters and stars

Process

Stars remove characters to their left

Output

Final string after all stars processed

Key Takeaway

🎯 Key Insight: Use a stack to simulate backspace behavior - push characters, pop on stars

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is treating stars as backspace operations. A stack naturally handles this by pushing characters and popping when encountering stars. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force String Manipulation	O(n²)	O(n)	Repeatedly find stars and remove them with their left character
Stack-Based Solution	O(n)	O(n)	Use a stack to process characters, popping when encountering stars

Brute Force String Manipulation — Algorithm Steps

Find the first star in the string
Find the closest non-star character to its left
Remove both characters
Repeat until no stars remain

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Star

Locate first star in string

Remove Pair

Remove star and character to its left

Repeat

Continue until no stars remain

Code -

solution.c — C

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

char* solution(char* s) {
    int len = strlen(s);
    char* result = malloc((len + 1) * sizeof(char));
    strcpy(result, s);
    
    while (strchr(result, '*') != NULL) {
        char* starPos = strchr(result, '*');
        int index = starPos - result;
        
        if (index > 0) {
            // Remove the character before the star and the star itself
            memmove(&result[index-1], &result[index+1], strlen(&result[index+1]) + 1);
        } else {
            // This shouldn't happen based on problem constraints
            memmove(&result[index], &result[index+1], strlen(&result[index+1]) + 1);
        }
    }
    return result;
}

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 of n characters, we may need to scan and rebuild the string

⚠ Quadratic Growth

Space Complexity

O(n)

Creating new strings during manipulation

⚡ Linearithmic Space

24.0K Views

Medium Frequency

~15 min Avg. Time

856 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

Brute Force String Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler