Removing Stars From a String

LeetCode 2390: Removing Stars From a String Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a two-pointer read/write technique to process the string in a single pass, decrementing the write pointer whenever a star is encountered to simulate a backspace.

In LeetCode 2390, you are given a string containing lowercase English letters and star characters (*). Each star acts as a backspace command, requiring you to remove the star itself and the closest non-star character to its left. Your task is to process all operations and return the final modified string. Because the input guarantees the operation is always possible, you never have to worry about removing a character from an empty sequence. Solving Removing Stars From a String efficiently is a popular interview question because it tests a candidate's ability to optimize sequential data manipulation.

Brute Force Approach for Removing Stars From a String

The most intuitive but naive way to solve this problem is to repeatedly search for a star and remove it along with the character immediately preceding it.

In this approach, you would iterate through the string to find the first occurrence of a *. Once found, you slice the string to exclude the star and the character at the index right before it, concatenate the remaining left and right halves, and repeat the process from the beginning of the new string until no stars remain.

function removeStarsNaive(s):
    while s contains '*':
        index = find first index of '*' in s
        s = s.substring(0, index - 1) + s.substring(index + 1)
    return s

Time Complexity Analysis & Failure Reason: This brute force approach operates in $O(N^2)$ time complexity. Finding the star takes up to $O(N)$ time, and creating a new string via slicing or concatenation also takes $O(N)$ time. In the worst-case scenario (e.g., a string of $N/2$ characters followed by $N/2$ stars), this results in quadratic time complexity. Given the problem constraints where the string length can be up to $10^5$, $O(N^2)$ operations will result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Two Pointer Patterns

To implement the optimal solution for interviews, we use a mutable sequence (like a character array or a mutable string, depending on the language) to avoid the overhead of immutable string concatenation.

1. Create a character array result of the same length as the input string s.
2. Initialize an integer write to 0. This will act as our writing pointer.
3. Iterate a read pointer from 0 to the length of s minus 1.
4. For each character at s[read]:
   • If the character is a *, decrement the write pointer by 1.
   • If the character is a lowercase letter, assign result[write] = s[read] and increment the write pointer by 1.
5. After the loop terminates, the valid characters are stored in result from index 0 to write - 1.
6. Construct and return a new string using the prefix of result up to the write pointer.

Execution Flow

Let's trace the algorithm using the string s = "leet**cod*e":

1. Initialize write = 0.
2. read = 0 ('l'): Not a star. result[0] = 'l', write becomes 1.
3. read = 1 ('e'): Not a star. result[1] = 'e', write becomes 2.
4. read = 2 ('e'): Not a star. result[2] = 'e', write becomes 3.
5. read = 3 ('t'): Not a star. result[3] = 't', write becomes 4. (Current valid prefix: "leet")
6. read = 4 ('*'): Is a star. Decrement write to 3. (Logical prefix: "lee")
7. read = 5 ('*'): Is a star. Decrement write to 2. (Logical prefix: "le")
8. read = 6 ('c'): Not a star. result[2] = 'c', write becomes 3. (Overwrites second 'e'. Prefix: "lec")
9. read = 7 ('o'): Not a star. result[3] = 'o', write becomes 4. (Overwrites 't'. Prefix: "leco")
10. read = 8 ('d'): Not a star. result[4] = 'd', write becomes 5.
11. read = 9 ('*'): Is a star. Decrement write to 4. (Logical prefix: "leco")
12. read = 10 ('e'): Not a star. result[4] = 'e', write becomes 5. (Overwrites 'd'. Prefix: "lecoe")
13. Loop ends. Return substring from 0 to write (length 5), which is "lecoe".

Proof of Correctness

The problem specifies that a star removes the closest non-star character to its left. In our sequential left-to-right traversal, the most recently written character represents the closest non-star character to the left of the current read position.

Decrementing the write pointer exactly drops this most recently written character from the valid output boundary. Because the problem constraints guarantee that the operation is always possible, we are mathematically assured that write will never drop below 0. Every valid character is kept, and every backspaced character is perfectly overwritten or excluded, strictly satisfying the rules of the problem.

Pattern Reuse Notes

The "Two Pointers - String Comparison with Backspaces" subpattern is highly reusable across string manipulation problems involving dynamic deletions. The following problems share the same pattern/subpattern:

• LeetCode 844: Backspace String Compare: Instead of returning the string, you use the exact same backspace logic (often traversing backwards to achieve $O(1)$ space) to compare if two strings resolve to the same text.
• LeetCode 1598: Crawler Log Folder: The directory navigation ../ acts identically to the * backspace character, moving your write pointer (or directory depth) backward while ignoring normal folder names.

Reference Implementation

C++ Solution for LeetCode 2390

In C++, strings are mutable, allowing us to perform the Two Pointer approach entirely in place for $O(1)$ auxiliary space.

1#include <string>
2
3class Solution {
4public:
5    std::string removeStars(std::string s) {
6        int write = 0;
7        
8        for (int read = 0; read < s.length(); ++read) {
9            if (s[read] == '*') {
10                write--; // Simulate backspace
11            } else {
12                s[write] = s[read]; // Overwrite and advance
13                write++;
14            }
15        }
16        
17        // Return the valid prefix of the modified string
18        return s.substr(0, write);
19    }
20};

Java Solution for LeetCode 2390

In Java, strings are immutable, so we must allocate a character array to act as our mutable buffer.

1class Solution {
2    public String removeStars(String s) {
3        char[] result = new char[s.length()];
4        int write = 0;
5        
6        for (int read = 0; read < s.length(); read++) {
7            char c = s.charAt(read);
8            if (c == '*') {
9                write--; // Simulate backspace
10            } else {
11                result[write] = c; // Overwrite and advance
12                write++;
13            }
14        }
15        
16        // Construct the final string from the valid boundaries
17        return new String(result, 0, write);
18    }
19}

Python Solution for LeetCode 2390

To strictly adhere to the Two Pointer array-manipulation pattern in Python (avoiding dynamic stack operations), we pre-allocate a list of characters.

1class Solution:
2    def removeStars(self, s: str) -> str:
3        # Pre-allocate array to strictly use read/write pointers
4        result = [''] * len(s)
5        write = 0
6        
7        for read in range(len(s)):
8            if s[read] == '*':
9                write -= 1  # Simulate backspace
10            else:
11                result[write] = s[read]  # Overwrite and advance
12                write += 1
13                
14        # Join only the valid prefix up to the write pointer
15        return "".join(result[:write])