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 ith piece.
Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
Example 1:
Input: colors = "AAABABB" Output: true Explanation: AAABABB -> AABABB Alice moves first. She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'. Now it's Bob's turn. Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'. Thus, Alice wins, so return true.
Example 2:
Input: colors = "AA" Output: false Explanation: Alice has her turn first. There are only two 'A's and both are on the edge of the line, so she cannot move on her turn. Thus, Bob wins, so return false.
Example 3:
Input: colors = "ABBBBBBBAAA" Output: false Explanation: ABBBBBBBAAA -> ABBBBBBBAA Alice moves first. Her only option is to remove the second to last 'A' from the right. ABBBBBBBAA -> ABBBBBBAA Next is Bob's turn. He has many options for which 'B' piece to remove. He can pick any. On Alice's second turn, she has no more pieces that she can remove. Thus, Bob wins, so return false.
Constraints:
1 <= colors.length <= 105colors consists of only the letters 'A' and 'B'One way to solve this question is to count the number of removable sequences for both Alice and Bob. A removable sequence is an occurrence of three consecutive 'A's for Alice and three consecutive 'B's for Bob. The player who has more removable sequences controls the pace of the game and can potentially use up all the opponent's moves.
This C solution iterates through the string, counting the possible moves for Alice ('AAA') and Bob ('BBB'). It uses a simple for loop, and the counts are compared to decide if Alice wins or not.
C++
Java
Python
C#
JavaScript
Time complexity is O(n), where n is the length of the string. Space complexity is O(1) as we use a fixed amount of space.
This approach involves using dynamic programming to determine the possible count of removable pieces for Alice and Bob. By maintaining an array, we can track the available moves dynamically, updating counts as pieces get removed, until no further moves are left for one player. This is more complex than the counting method but can offer deeper insight into game states.
This C solution uses dynamic programming to precompute possible moves for both Alice and Bob by filling arrays dp_a and dp_b. The arrays store cumulative possible moves at each step.
C++
Java
Python
C#
JavaScript
Time complexity is O(n) with space complexity of O(n) due to the arrays.
| Approach | Complexity |
|---|---|
| Count Removable Sequences | Time complexity is O(n), where n is the length of the string. Space complexity is O(1) as we use a fixed amount of space. |
| Dynamic Programming Approach | Time complexity is O(n) with space complexity of O(n) due to the arrays. |
Remove Colored Pieces if Both Neighbors are the Same Color - Leetcode 2038 - Python • NeetCodeIO • 9,848 views views
Watch 9 more video solutions →Practice Remove Colored Pieces if Both Neighbors are the Same Color with our built-in code editor and test cases.
Practice on FleetCode