✅96.44%🔥Easy Solution🔥Game Theory & Greedy
Problem Explanation:\n#### In this problem, you are given a string colors representing a line of colored pieces, where each piece is either colored \'A\' or \'B
# Problem Explanation:\n#### In this problem, you are given a string colors representing a line of colored pieces, where each piece is either colored \'A\' or \'B\'. Alice and Bob are playing a game where they take alternating turns removing pieces from the line. Alice goes first, and they have certain rules for removing pieces:\n\n- Alice can only remove a piece colored \'A\' if both its neighbors are also colored \'A\'. She cannot remove pieces that are colored \'B\'.\n- Bob can only remove a piece colored \'B\' if both its neighbors are also colored \'B\'. He cannot remove pieces that are colored \'A\'.\n- They cannot remove pieces from the edge of the line.\n\n#### The game continues until one of the players cannot make a move, and in that case, the other player wins.\n\n#### You need to determine, assuming both Alice and Bob play optimally, whether Alice can win the game or not.\n---\n# Solution Approach:\n#### The given solution approach uses a Counter object to count how many valid moves Alice can make and how many valid moves Bob can make. It iterates through the input string colors to count these moves.\n\n- The collections.Counter() is used to count the occurrences of characters in the string.\n- The groupby(colors) function groups consecutive characters in the string.\n- It iterates through the groups and counts how many \'A\'s and \'B\'s can be removed according to the game rules. Specifically, it counts the number of \'A\'s and \'B\'s that have at least two neighbors of the same color.\n- Finally, it compares the counts of valid moves for Alice (\'A\') and Bob (\'B\'). If Alice has more valid moves, it returns True; otherwise, it returns False.\n\n#### The idea is that if Alice can make more valid moves than Bob, she has a winning strategy because she will eventually force Bob into a position where he can\'t make a move.\n\n#### This solution works under the assumption that both players play optimally and is a good approach to solve the problem efficiently.\n\n\n---\n# Code\n```python []\nclass Solution:\n    def winnerOfGame(self, colors: str) -> bool:\n        c = collections.Counter()\n        for x, t in groupby(colors):\n            c[x] += max(len(list(t)) - 2, 0)\n\n        if c[\'A\'] > c[\'B\']:\n            return True\n        return False\n```\n```C# []\npublic class Solution {\n    public bool WinnerOfGame(string colors) {\n        int countA = 0;\n        int countB = 0;\n        \n        for (int i = 0; i < colors.Length; i++) {\n            char x = colors[i];\n            int count = 0;\n            \n            while (i < colors.Length && colors[i] == x) {\n                i++;\n                count++;\n            }\n            \n            if (x == \'A\') {\n                countA += Math.Max(count - 2, 0);\n            } else if (x == \'B\') {\n                countB += Math.Max(count - 2, 0);\n            }\n            \n            i--;\n        }\n\n        return countA > countB;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    bool winnerOfGame(string colors) {\n        map<char, int> c;\n        for (auto it = colors.begin(); it != colors.end(); ) {\n            char x = *it;\n            auto t = it;\n            while (t != colors.end() && *t == x) {\n                t++;\n            }\n            c[x] += max(int(distance(it, t) - 2), 0);\n            it = t;\n        }\n\n        if (c[\'A\'] > c[\'B\']) {\n            return true;\n        }\n        return false;\n    }\n};\n\n```\n```C []\nbool winnerOfGame(char *colors) {\n    int len = strlen(colors);\n    int countA = 0, countB = 0;\n\n    for (int i = 0; i < len; i++) {\n        char x = colors[i];\n        int count = 0;\n\n        while (i < len && colors[i] == x) {\n            i++;\n            count++;\n        }\n\n        if (x == \'A\') {\n            countA += (count - 2 > 0) ? count - 2 : 0;\n        } else if (x == \'B\') {\n            countB += (count - 2 > 0) ? count - 2 : 0;\n        }\n\n        i--;  \n    }\n\n    return countA > countB;\n}\n```\n```Java []\npublic class Solution {\n    public boolean winnerOfGame(String colors) {\n        Map<Character, Integer> c = new HashMap<>();\n        c.put(\'A\', 0);\n        c.put(\'B\', 0);\n        \n        for (int i = 0; i < colors.length(); i++) {\n            char x = colors.charAt(i);\n            int count = 0;\n            \n            while (i < colors.length() && colors.charAt(i) == x) {\n                i++;\n                count++;\n            }\n            \n            c.put(x, c.get(x) + Math.max(count - 2, 0));\n            i--;\n        }\n\n        return c.get(\'A\') > c.get(\'B\');\n    }\n}\n\n```\n```javascript []\nvar winnerOfGame = function(colors) {\n    let countA = 0;\n    let countB = 0;\n\n    for (let i = 0; i < colors.length; i++) {\n        const x = colors[i];\n        let count = 0;\n\n        while (i < colors.length && colors[i] === x) {\n            i++;\n            count++;\n        }\n\n        if (x === \'A\') {\n            countA += Math.max(count - 2, 0);\n        } else if (x === \'B\') {\n            countB += Math.max(count - 2, 0);\n        }\n\n        i--;\n    }\n\n    return countA > countB;\n};\n```\n```Typescript []\nfunction winnerOfGame(colors: string): boolean {\n    let countA = 0;\n    let countB = 0;\n\n    for (let i = 0; i < colors.length; i++) {\n        const x = colors[i];\n        let count = 0;\n\n        while (i < colors.length && colors[i] === x) {\n            i++;\n            count++;\n        }\n\n        if (x === \'A\') {\n            countA += Math.max(count - 2, 0);\n        } else if (x === \'B\') {\n            countB += Math.max(count - 2, 0);\n        }\n\n        i--;\n    }\n\n    return countA > countB;\n}\n\n```\n```Go []\nfunc winnerOfGame(colors string) bool {\n    countA := 0\n    countB := 0\n\n    for i := 0; i < len(colors); i++ {\n        x := colors[i]\n        count := 0\n\n        for i < len(colors) && colors[i] == x {\n            i++\n            count++\n        }\n\n        if x == \'A\' {\n            countA += max(count-2, 0)\n        } else if x == \'B\' {\n            countB += max(count-2, 0)\n        }\n\n        i--\n    }\n\n    return countA > countB\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\n```\n![9c6f9412-c860-47d6-9a2e-7fcf37ff3321_1686334926.180891.png](https://assets.leetcode.com/users/images/87958596-b3bb-481c-819f-27903c42329a_1696206059.2008882.png)\n\n
['Greedy', 'C', 'Game Theory', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'JavaScript', 'C#']