We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Colored Pieces if Both Neighbors are the Same Color

Number: 2149

Difficulty: Medium

Paid? No

Companies: J.P. Morgan, Amazon, Roblox, MathWorks

Problem Description

Given a string representing pieces in a line colored 'A' or 'B', two players (Alice and Bob) alternate turns removing pieces. Alice can only remove an 'A' if both its neighbors are also 'A', and Bob can only remove a 'B' if both its neighbors are 'B'. Pieces on the edges cannot be removed. The task is to determine if Alice wins, assuming both play optimally.

Key Insights

  • Only inner pieces (those not on the edge) can be removed.
  • For any index i (1 to n-2), if colors[i-1], colors[i], and colors[i+1] are all the same, then that move is available.
  • Count the total potential moves for Alice (for 'A') and for Bob (for 'B').
  • The outcome depends solely on comparing the counts; if Alice can make more moves than Bob, she wins.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few counters are used regardless of input size.

Solution

The solution involves iterating through the string (excluding the edge pieces) and counting the consecutive triplets for 'A' and 'B'. For every valid triplet:

  • If the triplet is "AAA", it is a potential move for Alice.
  • If the triplet is "BBB", it is a potential move for Bob. After counting, if the number of moves available to Alice (countA) is greater than those available to Bob (countB), then Alice wins. This approach avoids game simulation and leverages optimal play assumptions.

Code Solutions

# Python solution with detailed comments

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        # Initialize counters for Alice and Bob.
        countA = 0  # moves available for Alice
        countB = 0  # moves available for Bob
        
        # Iterate from index 1 to len(colors) - 2 since edges cannot be removed.
        for i in range(1, len(colors) - 1):
            # Check if left, current, and right pieces are the same.
            if colors[i - 1] == colors[i] == colors[i + 1]:
                # If the current piece is 'A', it's a potential move for Alice.
                if colors[i] == 'A':
                    countA += 1
                # Else if it is 'B', it's a potential move for Bob.
                else:
                    countB += 1
        
        # Alice can win if she has strictly more moves than Bob.
        return countA > countB
← Back to All Questions