Remove Colored Pieces If Both Neighbors Are The Same Color - Leetcode Solution

The problem "Remove Colored Pieces If Both Neighbors Are The Same Color" on LeetCode can be solved using a simple observation that whenever we remove a piece with the same color of its neighbors, the overall pattern remains the same, and we can continue removing such pieces until we cannot remove any more.

Here is the detailed solution with an explanation:

1. Traverse the string and identify pieces that have the same color as their neighbors.

2. Remove those pieces and update the string.

3. Repeat step 1 and 2 until we cannot remove any more pieces.

4. Check the remaining pieces and determine the winner.

Let's take an example to understand this better:

Example: Input: s = "AAABBC" Output: true

Explanation:

1. We can remove "AAA" and update the string to "BBC".
2. We can not remove any more pieces as no pieces have the same color as their neighbors.
3. The remaining string is "BBC", and as there is only one color left, the winner is player A.

Solution:

We will use two pointers to traverse the string, i and j, and a flag to determine the current player.

1. Initialize i and j to 0.

2. While i < j, keep moving j until we find a piece that has a different color than s[i] or j reaches the end of the string.

3. If j has reached the end of the string, check if (j-i) >= 2, if yes, then we can remove the pieces, update the string, and return true as player A wins.

4. Otherwise, move i = j and reset j to i+1.

5. Repeat steps 2 to 4 until we cannot remove any more pieces.

6. If there is only one color left, return true as player A wins, otherwise return false as player B wins.

Here is the python code implementation of the above solution:

class Solution: def winnerOfGame(self, colors: str) -> bool: n = len(colors) i, j = 0, 1 flag_A = True count_A, count_B = 0, 0

    while j < n:
        while j < n and colors[j] == colors[i]:
            j += 1
        
        if j-i >= 3 and flag_A:
            count_A += j-i-2
        elif j-i >= 3 and not flag_A:
            count_B += j-i-2
        
        i = j
        j = i+1
        
        flag_A = not flag_A
    
    if count_A > count_B:
        return True
    else:
        return False

The time complexity of the above solution is O(n), where n is the length of the input string.

1