2038. Remove Colored Pieces if Both Neighbors are the Same Color Medium

1/**
2 * [2038] Remove Colored Pieces if Both Neighbors are the Same Color
3 *
4 * 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.
5 * Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
6 * 
7 * 	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'.
8 * 	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'.
9 * 	Alice and Bob cannot remove pieces from the edge of the line.
10 * 	If a player cannot make a move on their turn, that player loses and the other player wins.
11 * 
12 * Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
13 *  
14 * Example 1:
15 * 
16 * Input: colors = "AAABABB"
17 * Output: true
18 * Explanation:
19 * A<u>A</u>ABABB -> AABABB
20 * Alice moves first.
21 * She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.
22 * Now it's Bob's turn.
23 * Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
24 * Thus, Alice wins, so return true.
25 * 
26 * Example 2:
27 * 
28 * Input: colors = "AA"
29 * Output: false
30 * Explanation:
31 * Alice has her turn first.
32 * There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
33 * Thus, Bob wins, so return false.
34 * 
35 * Example 3:
36 * 
37 * Input: colors = "ABBBBBBBAAA"
38 * Output: false
39 * Explanation:
40 * ABBBBBBBA<u>A</u>A -> ABBBBBBBAA
41 * Alice moves first.
42 * Her only option is to remove the second to last 'A' from the right.
43 * ABBBB<u>B</u>BBAA -> ABBBBBBAA
44 * Next is Bob's turn.
45 * He has many options for which 'B' piece to remove. He can pick any.
46 * On Alice's second turn, she has no more pieces that she can remove.
47 * Thus, Bob wins, so return false.
48 * 
49 *  
50 * Constraints:
51 * 
52 * 	1 <= colors.length <= 10^5
53 * 	colors consists of only the letters 'A' and 'B'
54 * 
55 */
56pub struct Solution {}
57
58// problem: https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/
59// discuss: https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/discuss/?currentPage=1&orderBy=most_votes&query=
60
61// submission codes start here
62
63impl Solution {
64    pub fn winner_of_game(colors: String) -> bool {
65        false
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_2038() {
77    }
78}
79