2038. Remove Colored Pieces if Both Neighbors are the Same Color - Explanation

Problem Link



1. Brute Force

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        s = list(colors)

        def removeChar(c):
            for i in range(1, len(s) - 1):
                if s[i] != c:
                    continue

                if s[i] == s[i + 1] == s[i - 1]:
                    s.pop(i)
                    return True
            return False

        while True:
            if not removeChar('A'):
                return False
            if not removeChar('B'):
                return True

        return False

Time & Space Complexity

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

2. Greedy + Two Pointers

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice = bob = l = 0

        for r in range(len(colors)):
            if colors[l] != colors[r]:
                l = r

            extra = r - l - 1
            if extra > 0:
                if colors[l] == 'A':
                    alice += 1
                else:
                    bob += 1

        return alice > bob

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

3. Greedy

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice, bob = 0, 0

        for i in range(1, len(colors) - 1):
            if colors[i - 1] == colors[i] == colors[i + 1]:
                if colors[i] == 'A':
                    alice += 1
                if colors[i] == 'B':
                    bob += 1

        return alice > bob

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.