100% Acceptance rate with O(n) Solution - Detailed explanation Ever Check it out
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem presents a game played between Alice and Bob on a line of colored pieces, r
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem presents a game played between Alice and Bob on a line of colored pieces, represented by the string colors. Each piece is colored either \'A\' or \'B\', and the players take alternating turns to remove pieces according to certain rules. Alice can remove a piece \'A\' if both its neighbors are also \'A\', and Bob can remove a piece \'B\' if both its neighbors are also \'B\'. The game continues until a player cannot make a valid move, and the one who cannot move loses the game. The task is to determine if Alice will win or if Bob will win when both play optimally.\n\n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize two variables, aliceWins and bobWins, to keep track of the number of consecutive valid moves each player can make.\n\n2. Iterate through the string colors from the second character to the second-to-last character. This ensures that we do not consider the edge pieces (the first and last characters), as the rules for removal require pieces to have both neighbors.\n\n3. For each position i, check if there are three consecutive \'A\'s or three consecutive \'B\'s. If there are, increment the corresponding counter (aliceWins or bobWins). This means that Alice can remove the \'A\' piece or Bob can remove the \'B\' piece at that position.\n\n4. After iterating through the string, compare the counts of aliceWins and bobWins. If aliceWins is greater than bobWins, Alice wins the game, so return true. Otherwise, Bob wins the game, so return false.\n\n---\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this code is O(n), where n is the length of the input string colors. This is because we iterate through the string once, visiting each character once.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(1) because we only use a constant amount of extra space to store the two counters aliceWins and bobWins. Regardless of the size of the input string, the space required remains constant.\n\n---\n\n# Code\n```\nclass Solution {\npublic:\n    bool winnerOfGame(string colors) {\n        int n = colors.length();\n        int aliceWins = 0, bobWins = 0;\n        \n        // Count the number of consecutive \'A\'s and \'B\'s.\n        for (int i = 1; i < n - 1; ++i) {\n            if (colors[i - 1] == \'A\' && colors[i] == \'A\' && colors[i + 1] == \'A\') {\n                aliceWins++;\n            } else if (colors[i - 1] == \'B\' && colors[i] == \'B\' && colors[i + 1] == \'B\') {\n                bobWins++;\n            }\n        }\n        \n        // Alice starts, so if she has more opportunities to remove \'A\', she wins.\n        if (aliceWins > bobWins) {\n            return true;\n        }\n        \n        return false;\n    }\n};\n\n```
['Math', 'String', 'Dynamic Programming', 'Greedy', 'C', 'Game Theory', 'Python', 'C++', 'Java', 'Python3']