Leetcode 2390: Removing Stars From a String

Input: The input consists of a string `s` that contains lowercase English letters and stars (`*`).

Example: Input: s = 'abc*def*gh*'

Constraints:

• 1 <= s.length <= 10^5

• s consists of lowercase English letters and stars `*`.

• The operation above can be performed on s.

Output: Return the string after all stars have been removed by performing the operation as described.

Example: Output: 'abgh'

Constraints:

Goal: The goal is to remove the closest character to each star from left to right until all stars are removed.

Steps:

• 1. Traverse the string and for each star, remove the closest non-star character to its left.

• 2. After each removal, adjust the string accordingly and continue the operation.

• 3. Repeat the process until all stars are removed.

Goal: The string can have up to 100,000 characters and consists of lowercase English letters and stars.

Steps:

• The operation should be performed on strings of length up to 10^5.

Assumptions:

• There will always be a non-star character to remove before each star.

• Input: Input: s = 'abc*def*gh*'

• Explanation: In the first operation, remove 'c' before the first star, resulting in 'ab*def*gh*'. Then remove 'f' before the second star, resulting in 'abdef*gh*'. Finally, remove 'g' before the last star, leaving 'abgh'.

• Input: Input: s = 'abc*****'

• Explanation: In this case, all characters are removed sequentially one by one before each star, resulting in an empty string.

Approach: We will iterate through the string, maintain a pointer for the current position, and simulate the removal of the closest characters before each star.

Observations:

• We need to efficiently track the position of each star and remove the correct character from left to right.

• A stack-like approach would be useful to track the characters as we traverse through the string. When encountering a star, we can pop the last added character.

Steps:

• 1. Initialize an empty list `res` to simulate a stack.

• 2. Traverse each character of the string `s`.

• 3. If the character is not a star, append it to `res`.

• 4. If the character is a star, remove the last character added to `res`.

• 5. After processing the entire string, the list `res` will contain the final result.

Empty Inputs:

• If the input string is empty, return an empty string.

Large Inputs:

• Ensure the solution can handle the maximum input size efficiently (up to 100,000 characters).

Special Values:

• Handle cases where stars are placed at the beginning or end of the string.

Constraints:

• Make sure the solution works within the time limits for large inputs.

string removeStars(string s) {
    int j = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] != '*') s[j++] = s[i];
        else {
            j--;
        }
    }
    return s.substr(0, j);
}

1 : Function Declaration

string removeStars(string s) {

Function declaration that takes a string `s` and returns a modified string with all '*' characters removed.

2 : Variable Initialization

    int j = 0;

Initialize an integer `j` to track the position where valid characters should be placed in the string.

3 : Loop

    for(int i = 0; i < s.size(); i++) {

Loop through the string `s`, from the beginning to the end, using `i` as the index.

4 : Character Check

        if(s[i] != '*') s[j++] = s[i];

If the current character is not '*', copy it to the position `j` and increment `j` to the next valid position.

5 : Star Removal

        else {

If the current character is a '*', enter the else block to handle its removal.

6 : Pointer Adjustment

            j--;

Decrement `j` to overwrite the last valid character, effectively removing the '*' character.

7 : Return Substring

    return s.substr(0, j);

Return the modified string by extracting the substring from the beginning up to the position `j`, which contains all valid characters.

Best Case: O(n) where n is the length of the string.

Average Case: O(n) where n is the length of the string.

Worst Case: O(n) where n is the length of the string.

Description: The algorithm processes each character exactly once, resulting in a time complexity of O(n).

Best Case: O(n) for storing the intermediate results in the stack.

Worst Case: O(n) for storing the intermediate results in the stack.

Description: The space complexity is O(n) due to the storage needed for the stack that holds the resulting characters.

Leetcode 2390: Removing Stars From a String

Explore →