Removing Stars From a String

How it works

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.

Steps

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

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    string removeStars(string s) {
        int l = 0;

        for (int r = 0; r < s.size(); r++) {
            if (s[r] == '*') {
                l--;
            } else {
                s[l] = s[r];
                l++;
            }
        }
        return s.substr(0, l);
    }
};