2390. Removing Stars From a String - Explanation

1. Brute Force

Intuition

Each star removes the closest non-star character to its left. The simplest approach is to simulate this process directly: scan for a star, remove it along with the character before it, then repeat until no more removals are possible. This is straightforward but inefficient because each removal requires rebuilding the string. In the loop, we iterate with index i to find each star.

Algorithm

Loop until no changes occur:
- Scan the string from left to right using index i.
- When a star is found at s[i] with a non-star character before it, remove both characters.
- Restart the scan.
Return the final string.

class Solution:
    def removeStars(self, s: str) -> str:
        while True:
            flag = False
            for i in range(1, len(s)):
                if s[i] == '*' and s[i - 1] != '*':
                    s = s[:i - 1] + s[i + 1:]
                    flag = True
                    break
            if not flag:
                break
        return s

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Brute Force (Optimized)

Intuition

Instead of restarting the scan from the beginning after each removal, we can continue from where we left off, adjusting our position backward after removing characters. This avoids redundant scanning of already-processed portions, though string manipulation still takes linear time per removal. We track the current position with i and the length with n.

Algorithm

Initialize index i = 0 and n = len(s).
While i < n:
- If s[i] is a star and s[i-1] is not a star, remove both and decrement i by 2.
- Otherwise, increment i.
Return the final string.

class Solution:
    def removeStars(self, s: str) -> str:
        n = len(s)
        i = 0
        while i < n:
            if i and s[i] == '*' and s[i - 1] != '*':
                s = s[:i - 1] + s[i + 1:]
                n -= 2
                i -= 2
            i += 1
        return s

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Stack

Intuition

A star removes the most recently added non-star character, which is exactly what a stack does with pop operations. As we scan the string with index i, we push non-star characters c onto the stack. When we encounter a star, we pop the top element. The remaining stack contents form the answer.

Algorithm

Initialize an empty stack.
For each character c in the string:
- If it is a star and the stack is not empty, pop from the stack.
- Otherwise, push c onto the stack.
Join the stack contents into a string and return it.

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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Two Pointers

Intuition

We can avoid extra space by using the input array itself. A left pointer l tracks where the next valid character should be placed, while a right pointer r scans through the string. For stars, we decrement l to "undo" the last character. For regular characters, we write them at position l and increment l. The result is the substring from 0 to l.

Algorithm

Convert the string to a character array and initialize l = 0.
For each index r:
- If s[r] is a star, decrement l.
- Otherwise, copy s[r] to s[l] and increment l.
Return the substring from index 0 to l.

class Solution:
    def removeStars(self, s: str) -> str:
        l = 0
        s = list(s)

        for r in range(len(s)):
            if s[r] == '*':
                l -= 1
            else:
                s[l] = s[r]
                l += 1

        return ''.join(s[:l])

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ or $O(n)$ depending on the language.

Common Pitfalls

Popping from an Empty Stack

While the problem guarantees valid input where every star has a corresponding character to remove, defensive coding should still check for an empty stack before popping. In variations of this problem or with malformed input, popping from an empty stack causes runtime errors.

Modifying the String While Iterating

In the brute force approach, removing characters shifts indices and changes the string length. Continuing iteration without adjusting the index leads to skipped characters or out-of-bounds access. Either restart iteration after each modification or adjust indices carefully.

Negative Index in Two-Pointer Approach

When a star decrements the left pointer l, it can become negative if there are leading stars (though the problem constraints prevent this). In general scenarios, always ensure l stays non-negative before decrementing, or validate input constraints explicitly.