Remove Colored Pieces if Both Neighbors are the Same Color

Medium

MathWorks

2 views

Topics:

ArraysStringsGreedy Algorithms

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.

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 <= 10⁵
colors consists of only the letters 'A' and 'B'

Try coding it in LeetCode

Remove Colored Pieces if Both Neighbors are the Same Color

Medium

MathWorks

2 views

Topics:

ArraysStringsGreedy Algorithms

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.

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 <= 10⁵
colors consists of only the letters 'A' and 'B'

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `colors` string?
Can the `colors` string be empty or null?
Besides 'A' and 'B', can the `colors` string contain any other characters?
If Alice and Bob have the same number of possible moves, is that a win for Alice (tie goes to Alice), or does Alice need strictly more moves to win?
Could you provide a few examples of inputs and expected outputs to confirm my understanding of the rules?

Brute Force Solution

Approach

We're playing a game where players remove colored pieces. The brute force way means we try absolutely every possible move sequence and see who wins each time. We then determine who wins overall by analyzing all these game outcomes.

Here's how the algorithm would work step-by-step:

Start with the initial arrangement of colored pieces.
Consider every possible move Alice can make first (if it's her turn).
For each of Alice's moves, consider every possible move Bob can then make.
Continue alternating turns, exploring every possible move for each player, until the game ends (one player can't move).
For each complete game played out, determine who won that particular game.
After exploring absolutely all possible game scenarios, count how many times Alice wins and how many times Bob wins.
Declare the player with the most wins across all the explored games as the overall winner.

Code Implementation

def remove_colored_pieces_brute_force(colors):
    def find_possible_moves(current_colors, player):
        possible_moves = []
        for index in range(1, len(current_colors) - 1):
            if current_colors[index - 1] == player and current_colors[index + 1] == player and current_colors[index] == player:
                possible_moves.append(index)
        return possible_moves

    def game_winner(current_colors, alice_turn):
        alice_wins = 0
        bob_wins = 0

        possible_moves = find_possible_moves(current_colors, 'A' if alice_turn else 'B')

        # If there are no moves, the other player wins
        if not possible_moves:
            return 'B' if alice_turn else 'A'

        for move in possible_moves:
            new_colors = current_colors[:move] + current_colors[move+1:]
            winner = game_winner(new_colors, not alice_turn)
            if winner == 'A':
                alice_wins += 1
            else:
                bob_wins += 1

        if alice_wins >= bob_wins:
            return 'A'
        else:
            return 'B'

    # Count wins in all scenarios, declare winner
    alice_wins_total = 0
    bob_wins_total = 0
    
    winner = game_winner(colors, True)
    if winner == 'A':
        alice_wins_total += 1
    else:
        bob_wins_total += 1

    # Determine overall winner
    if alice_wins_total > bob_wins_total:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores every possible move sequence. In the worst case, each player might have multiple valid moves at each turn. The number of possible game states grows exponentially with the length of the input string n, as each move branches out into multiple new game states. Therefore, the total number of game states explored is proportional to 2 raised to the power of n. This leads to a time complexity of O(2^n).

Space Complexity

O(N!) – The brute force approach explores every possible move sequence. The recursion depth can reach N, where N is the length of the input string 'colors'. At each level of recursion, the algorithm explores all possible moves for the current player. In the worst-case scenario, where the number of possible moves is significant at each level, the number of branches in the recursion tree grows factorially. Therefore, the space complexity, primarily due to the recursion call stack, becomes O(N!).

Optimal Solution

Approach

The key to this problem is to focus on the potential moves each player can make instead of simulating the entire game. A player can only make a move if they are surrounded by their own color. By counting the number of possible moves for each player, we can quickly determine the winner.

Here's how the algorithm would work step-by-step:

Go through the entire sequence of colored pieces.
Count the number of possible moves for the first player by checking if any of their pieces are surrounded by two pieces of their own color.
Count the number of possible moves for the second player in the same way.
Compare the number of moves each player can make.
If the first player has more possible moves, they win.
If the second player has more possible moves, they win.
If they have the same number of possible moves, it's a tie, and the second player wins.

Code Implementation

def winnerOfGame(colors):
    alice_moves = 0
    bob_moves = 0

    # Iterate through the colors to count moves.
    for i in range(1, len(colors) - 1):
        if colors[i - 1] == colors[i] == colors[i + 1]:
            # Increment Alice's moves if the color is 'A'.
            if colors[i] == 'A':

                alice_moves += 1
            # Increment Bob's moves if the color is 'B'.
            else:

                bob_moves += 1

    # Determine the winner based on the number of moves.
    if alice_moves > bob_moves:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input string of length n, representing the colored pieces, only once. During this single pass, it checks each piece to determine if it is surrounded by two pieces of the same color. The checks involve constant-time comparisons for each piece. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input string but does not create any auxiliary data structures that scale with the input size N (the length of the colors string). It only uses a few integer variables to store the counts of possible moves for each player. Therefore, the space used is constant, irrespective of the input size.

Edge Cases

Case	How to Handle
Null or empty input string	Return false immediately since neither player can make any moves.
String with length less than 3	Return false immediately since no piece can have two neighbors.
String with all 'A's or all 'B's	No moves are possible, so return false.
String with alternating 'A's and 'B's (e.g., 'ABABAB')	No moves are possible, so return false.
String with a long sequence of the same color (e.g., 'AAAAAAA')	The solution should efficiently count the number of removable pieces in the sequence without exceeding time limits.
String with only one possible move for Alice or Bob	The algorithm should correctly identify and count only that single possible move.
Very long input string (close to the maximum allowed length)	Ensure that the solution uses O(n) time and space complexity to avoid timeouts.
String starts or ends with a sequence of repeating characters	The algorithm needs to correctly handle boundary conditions when calculating possible moves.