2390. Removing Stars From a String

Description

Given a string s that consists of characters and stars ('*'), the task is to remove the characters that are immediately before each star. Each '*' can only remove the preceding character, and once removed, it is no longer part of the string. Return the final string after performing all the operations.

Intuition

The problem can be intuitively solved by thinking of the '*' characters as backspaces. Each star deletes the last added character, so a stack or stack-like approach will help us efficiently simulate this process.

Approach

1. Iteration and Stack Mechanism: - Traverse the string from left to right. - Use a stack or a similar structure to keep track of characters. - When encountering a regular character, push it onto the stack or append it to the result. - When encountering a '*', remove the last character from the stack or result. - After processing the entire string, the stack or the result will contain the desired string.
2. Implementation Details: - Use a stack or a StringBuilder in Java or a string in C++ to efficiently add and remove characters. - The stack will represent the current state of the string after processing all deletions.

Complexity

Time Complexity:

O(n), where n is the length of the string s. We iterate through each character once.

Space Complexity:

O(n), in the worst case, where n characters could be stored in the stack or result if there are no stars.

Code

C++

class Solution {
public:
    string removeStars(string s) {
        string result;
        for (char c : s) {
            if (c == '*') {
                if (!result.empty()) {
                    result.pop_back();
                }
            } else {
                result.push_back(c);
            }
        }
        return result;
    }
};

Python

class Solution:
    def removeStars(self, s: str) -> str:
        self.ctr = 0
        return self.recurse(s, 0)

    def recurse(self, s: str, i: int) -> str:
        if i >= len(s):
            return ""
        result = self.recurse(s, i + 1)
        if s[i] == '*':
            self.ctr += 1
            return result
        elif self.ctr > 0:
            self.ctr -= 1
            return result
        else:
            return s[i] + result

Java

class Solution {
    public String removeStars(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '*') {
                if (result.length() > 0) {
                    result.deleteCharAt(result.length() - 1);
                }
            } else {
                result.append(c);
            }
        }
        return result.toString();
    }
}

JavaScript

var removeStars = function (s) {

    let ctr = 0;
    return (function recurse(i) {
        
        if (!s[i]) return "";
        const result = recurse(i + 1);
        if (s[i] == '*') {
            ctr++;
            return result
        } else if (ctr) {
            ctr--;
            return result;
        } else return s[i] + result;
    })(0);
};