Leetcode 2038: Remove Colored Pieces if Both Neighbors are the Same Color
You are given a string
colors consisting of two types of pieces, ‘X’ and ‘Y’, arranged in a line. Two players, Alex and Brian, play a game where they take turns removing pieces from the string. Alex moves first and can only remove a piece ‘X’ if both its neighbors are also ‘X’. Similarly, Brian can only remove a piece ‘Y’ if both its neighbors are also ‘Y’. Neither player can remove edge pieces. If a player cannot make a move, they lose. Determine whether Alex wins the game if both players play optimally.Problem
Approach
Steps
Complexity
Input: The input is a single string `colors` of length `n`, where `colors[i]` is either 'X' or 'Y', representing the pieces.
Example: "XXYXXY"
Constraints:
• 1 <= colors.length <= 100000
• colors consists only of the characters 'X' and 'Y'
Output: Return `true` if Alex wins the game, or `false` if Brian wins the game.
Example: true
Constraints:
• The result must be computed efficiently due to the constraints on input size.
Goal: Determine the winner by counting the number of valid moves for each player and checking if Alex has more valid moves than Brian.
Steps:
• 1. Iterate through the string `colors`.
• 2. Count all segments of three consecutive 'X's (valid moves for Alex).
• 3. Count all segments of three consecutive 'Y's (valid moves for Brian).
• 4. Compare the counts: if Alex's count is greater than Brian's, return `true`; otherwise, return `false`.
Goal: The problem's constraints ensure that the input is manageable for efficient computation.
Steps:
• 1 <= colors.length <= 100000
• colors consists only of 'X' and 'Y'.
Assumptions:
• Players play optimally.
• The string always contains at least one 'X' or 'Y'.
• Input: "XXYXYXX"
• Explanation: Alex removes the middle 'X' from "XXYXYXX" to get "XYXYXX". Brian has no valid moves, so Alex wins. The function returns `true`.
• Input: "YYXXYY"
• Explanation: Neither Alex nor Brian has a valid move, so Brian wins because Alex cannot make the first move. The function returns `false`.
Approach: Count the number of valid moves for each player and determine the winner by comparing the counts.
Observations:
• A player can only remove a piece surrounded by identical neighbors.
• The game ends when neither player can make a valid move.
• Counting valid moves for each player provides a direct way to determine the winner.
Steps:
• 1. Initialize counters for Alex and Brian's moves.
• 2. Loop through the string, checking for sequences of three consecutive identical characters.
• 3. Increment Alex's counter for 'XXX' sequences and Brian's counter for 'YYY' sequences.
• 4. Compare the counters and return the result.
Empty Inputs:
• Not applicable due to constraints.
Large Inputs:
• Strings with length close to the upper limit (100000).
Special Values:
• Strings where all characters are the same ('XXXXXX' or 'YYYYYY').
• Strings with no valid moves for either player ('XYXYXY').
Constraints:
• Must handle strings with maximum length efficiently.
bool winnerOfGame(string colors) {
int a = 0, b = 0;
for(int i = 1; i < colors.size() - 1; i++) {
if(colors[i - 1] == colors[i] && colors[i] == colors[i+1]) {
if(colors[i] == 'A') a++;
else b++;
}
}
return a > b;
}
1 : Function Definition
bool winnerOfGame(string colors) {
This line defines the function `winnerOfGame` which takes a string `colors` as input. The function determines if player 'A' wins the game by counting consecutive matching colors.
2 : Variable Initialization
int a = 0, b = 0;
Here, two variables `a` and `b` are initialized to zero. They will be used to count the number of consecutive matching color pairs for players 'A' and 'B' respectively.
3 : Loop
for(int i = 1; i < colors.size() - 1; i++) {
This `for` loop iterates over the `colors` string, starting from the second character and stopping at the second-to-last character to check for consecutive matching colors.
4 : Condition Check
if(colors[i - 1] == colors[i] && colors[i] == colors[i+1]) {
This `if` statement checks if the current character and its adjacent characters (previous and next) are the same. If true, it means there is a consecutive match of three identical colors.
5 : Increment Counter
if(colors[i] == 'A') a++;
If the consecutive matching colors belong to player 'A' (i.e., the character is 'A'), the counter `a` is incremented by 1.
6 : Increment Counter
else b++;
If the consecutive matching colors belong to player 'B' (i.e., the character is 'B'), the counter `b` is incremented by 1.
7 : Return Statement
return a > b;
The function returns `true` if player 'A' has more consecutive matching colors than player 'B'. Otherwise, it returns `false`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm processes each character of the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The algorithm uses constant extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus