2390. Removing Stars From a String - Explanation

Problem Link



1. Brute Force

class Solution:
    def removeStars(self, s: str) -> str:
        while True:
            flag = False
            for i in range(1, len(s)):
                if s[i] == '*' and s[i - 1] != '*':
                    s = s[:i - 1] + s[i + 1:]
                    flag = True
                    break
            if not flag:
                break
        return s

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

2. Brute Force (Optimized)

class Solution:
    def removeStars(self, s: str) -> str:
        n = len(s)
        i = 0
        while i < n:
            if i and s[i] == '*' and s[i - 1] != '*':
                s = s[:i - 1] + s[i + 1:]
                n -= 2
                i -= 2
            i += 1
        return s

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

3. Stack

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for c in s:
            if c == "*":
                stack and stack.pop()
            else:
                stack.append(c)
        return "".join(stack)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Two Pointers

class Solution:
    def removeStars(self, s: str) -> str:
        l = 0
        s = list(s)

        for r in range(len(s)):
            if s[r] == '*':
                l -= 1
            else:
                s[l] = s[r]
                l += 1

        return ''.join(s[:l])

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the language.