You are given a string s
, which contains stars *
. In one operation, you can:
s
.Return the string after all stars have been removed.
Note: The input will be generated such that the operation is always possible, and the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation:
Performing the removals from left to right:
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 <= 10^5
, s
consists of lowercase English letters and stars *
, and the operation above can be performed on s
.
A brute force solution would involve iterating through the string, and for each star encountered, searching backwards for the closest non-star character and removing both. This process is repeated until all stars are removed.
Consider the string s = "leet**cod*e"
lee*cod*e
lecod*e
lecoe
def remove_stars_naive(s):
s_list = list(s)
stars_removed = 0
i = 0
while i < len(s_list):
if s_list[i] == '*':
# Find the closest non-star character to the left
j = i - 1
while j >= 0 and s_list[j] == '*':
j -= 1
if j >= 0:
del s_list[j]
del s_list[i - 1]
i -= 1
else:
i += 1
return "".join(s_list)
O(N^2) in the worst case, where N is the length of the string. Removing characters from a list is O(N) operation.
O(N) because we convert the string to a list.
A more efficient solution can be achieved using a stack. We iterate through the string. If we encounter a non-star character, we push it onto the stack. If we encounter a star, we pop a character from the stack (if the stack is not empty). Finally, we construct the result string from the stack.
Consider the string s = "leet**cod*e"
def remove_stars_optimal(s):
stack = []
for char in s:
if char == '*':
if stack:
stack.pop()
else:
stack.append(char)
return ''.join(stack)
O(N), where N is the length of the string because we iterate through the string once.
O(N) in the worst case, as the stack could potentially store all non-star characters if there are no stars or the stars appear at the end of the string.
The provided optimal solution handles all these cases correctly.