Removing Stars From a String
Problem Description
You are given a string s, which contains stars *.
In one operation, you can:
- Choose a star in
s. - Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
- The input will be generated such that the operation is always possible.
- It can be shown that the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
Constraints:
- 1 <= s.length <= 105
sconsists of lowercase English letters and stars*.- The operation above can be performed on
s.
Solve it on LeetCode
Approaches
1. Brute Force Using Stack
We can solve this problem using a stack to handle the character additions and star removals efficiently.
Intuition:
- Traverse the string character by character.
- Use a stack to keep track of characters that have been added.
- When encountering a star ('*'), pop the top element from the stack if it's not empty. This simulates the action of the star removing the preceding character.
- Continue this process until the entire string is traversed.
- Finally, convert the stack back to a string which represents the transformed version of the original string without the stars and the characters removed by them.
Steps:
- Initialize a stack to hold characters.
- Traverse each character in the string.
- If the character is not '*', push it onto the stack.
- If the character is '*', pop the top character from the stack if the stack is not empty.
- Convert the stack to a string and return it.
Code:
- Time Complexity: O(n) - We iterate through the string once, where n is the number of characters in the string.
- Space Complexity: O(n) - In the worst case, all characters (except stars) are stored in the stack.
2. Optimized In-place Modification
We can enhance the efficiency by using a similar logic to sweep through the array, using in-place modifications to reduce the auxiliary space.
Intuition:
- Instead of using a data structure like stack, use a characteristic of a string where stars remove characters.
- Traverse the string while maintaining an index to record the position at which the current non-star character should be placed.
- For each non-star character, place it at the current index and increment the index.
- For a star ('*'), decrement the index to account for removing the previous character.
Steps:
- Convert the string into a character array.
- Use variable
indexto track the write position for valid characters. - Iterate over the character array:
- For non-star characters, place the character at the current
indexand then incrementindex. - For a star, decrement
index. - Construct the resultant string using the valid portion of the character array up to
index.
Code:
- Time Complexity: O(n) - We make a single pass over the string.
- Space Complexity: O(1) - No additional space is required beyond a few variables.