Taro Logo

Removing Stars From a String

Medium
Amazon logo
Amazon
2 views
Topics:
StringsStacks

You are given a string s, which contains stars *. In one operation, you can:

  1. Choose a star in s.
  2. 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, 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:

  • The closest character to the 1st star is 't' in "leetcode". s becomes "leecod*e".
  • The closest character to the 2nd star is 'e' in "leecode". s becomes "lecode".
  • The closest character to the 3rd star is 'd' in "lecode". 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 <= 10^5, s consists of lowercase English letters and stars *, and the operation above can be performed on s.

Solution


Naive Solution

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.

Example

Consider the string s = "leet**cod*e"

  1. First star: Remove 't', resulting in lee*cod*e
  2. Second star: Remove 'e', resulting in lecod*e
  3. Third star: Remove 'd', resulting in lecoe

Code (Python)

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)

Time Complexity

O(N^2) in the worst case, where N is the length of the string. Removing characters from a list is O(N) operation.

Space Complexity

O(N) because we convert the string to a list.

Optimal Solution

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.

Example

Consider the string s = "leet**cod*e"

  1. 'l', 'e', 'e', 't' are pushed onto the stack.
  2. First '*': 't' is popped.
  3. Second '*': 'e' is popped.
  4. 'c', 'o', 'd' are pushed onto the stack.
  5. '*': 'd' is popped.
  6. 'e' is pushed onto the stack.
  7. The stack contains 'l', 'e', 'c', 'o', 'e'.

Code (Python)

def remove_stars_optimal(s):
    stack = []
    for char in s:
        if char == '*':
            if stack:
                stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Time Complexity

O(N), where N is the length of the string because we iterate through the string once.

Space Complexity

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.

Edge Cases

  1. Empty String: An empty string should return an empty string.
  2. String with only stars: e.g., "*****", should return an empty string.
  3. No stars in the string: e.g., "abcdef", should return the original string.
  4. Stars at the beginning: e.g., "**abc", some characters will be removed from the start.

The provided optimal solution handles all these cases correctly.