Problem Description
There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the i-th piece. Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
- Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
- Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
- Alice and Bob cannot remove pieces from the edge of the line.
- If a player cannot make a move on their turn, that player loses and the other player wins.
Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
Key Insights
- The game revolves around the ability to remove pieces based on their neighbors' colors.
- Players can only remove inner pieces (not edge ones), which means the game state can be slightly restrictive.
- The outcome depends on the initial configuration of pieces and the moves taken during the game.
- Both players will always try to maximize their winning chances while minimizing the opponent's options.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The solution involves simulating the game with a focus on the removal rules for Alice and Bob. We can iterate through the string of colors to find removable pieces for both players. The key is to count how many pieces Alice and Bob can potentially remove. If Alice has more potential removals than Bob, she is likely to win; otherwise, Bob will win.
The algorithm can be implemented using a greedy approach, keeping track of the number of removable pieces for each player until no more moves can be made.