【Video】How we think about a solution - Python, JavaScript, Java, C++
Welcome to my post! This post starts with "How we think about a solution". In other words, that is my thought process to solve the question. This post explains 
Welcome to my post! This post starts with "How we think about a solution". In other words, that is my thought process to solve the question. This post explains how I get to my solution instead of just posting solution codes or out of blue algorithms. I hope it is helpful for someone.\n\n# Intuition\nsliding by 3 characters\n\n---\n\n# Solution Video\n\nhttps://youtu.be/XxWF-hv9Ltk\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,577\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n# Approach\n### How we think about a solution\n\nAlice and Bob can remove their own characters if they meet the conditions below\n\n---\n\n\n- 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\'.\n- 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\'.\n- Alice and Bob cannot remove pieces from the edge of the line.\n\n---\n\nIn this problem, there are countless ways to choose A or B. In such cases, I always start by considering the simplest input to derive patterns or algorithms.\n\nLet\'s think about this case.\n\n```\nInput: "AAA"\n"Alice definitely will win the game."\n```\n\nHow about this.\n```\nInput: "AAABBB"\n"Alice will lose the game."\n```\n\nHow about this.\n```\nInput: "AAABBBAAA"\n"Alice will win the game."\n```\n\n---\n\u2B50\uFE0F Points\n\n- From the simple examples above, Seems like the person with the most occurrences of three identical characters in a row wins.\n\n---\n\nHow about this.\n```\nInput: "AAAABBB"\n\nAAAABBB\n -\nAAABBB\n    -\nAAABB\n -\nAABB\n\n"Alice will win the game."\n```\n\n\nHow about this\n\n```\nInput: "AAABBBA"\n\nAAABBBA\n -\nAABBBA\n   -\nAABBA\n\n"Alice will lose the game."\n```\n\n---\n\u2B50\uFE0F Points\n\n- When there are four or more identical characters in a row, Alice can increase the count by sliding one by one.\n\nFor example,\n\nAAA = 1\nAAAA = 2\nAAAAA = 3\nAAAAAA = 4\n\n- It doesn\'t seem to matter where to erase from. Because if you have "B" like this\n```\nBBBAAAAAABBB\nBBBAAABAAAABBB\n```\n**the order of A and B is never changed**, so it doesn\'t affect the results.\n\n---\n\nFrom this idea, we should count number of 3 adjacent identical characters, then if Alice\'s count is greater than Bob\'s count, Alice will win the game.\n\nLet\'s see one by one.\n```\nInput: "ABBBBBBBAAA"\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 0\n---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 1\n ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 2\n  ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 3\n   ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 4\n    ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 5\n     ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 5\n      ---\n```\n```\nABBBBBBBAAA = Alice: 0, Bob: 5\n       ---\n```\n```\nABBBBBBBAAA = Alice: 1, Bob: 5\n        ---\n```\n```\nOutput: false\n```\n\nOne more edge case,\n\n\n---\n\u2B50\uFE0F Points\n\nAlice goes first, so if Alice\'s count is equal to Bob\'s count, Alice will lose the game.\n\n---\n\n\nBut we can deal with the edge case with `Alice > Bob` instead of `Alice >= Bob` because they are equal, Bob will win the game and we should return `false`. we can return `true` if we only meet `Alice > Bob`.\n\nLet\'s see real algorithm\n\n### Algorithm Overview:\n1. Check the length of the `colors` string to determine if it\'s less than or equal to 2.\n2. Initialize counters for Alice and Bob\'s streaks.\n3. Iterate through the \'colors\' string, excluding the first and last characters, checking for streaks.\n\n### Detailed Explanation:\n1. Check if the length of the `colors` string is less than or equal to 2:\n   - If the length is 2 or less, return False since it\'s not possible to determine a winner.\n\n2. Initialize counters for Alice and Bob\'s streaks:\n   - Set `alice_count` and `bob_count` to `0` to keep track of consecutive colors for Alice and Bob, respectively.\n\n3. Iterate through the `colors` string to find streaks:\n   - Start iterating from the second character to the second-to-last character of the `colors` string.\n   - Check if the current color and its adjacent neighbors are the same (a streak of three consecutive colors):\n     - If a streak of `AAA` is found, increment `alice_count`.\n     - If a streak of `BBB` is found, increment `bob_count`.\n\n4. Determine the winner:\n   - Compare `alice_count` and `bob_count`:\n     - If Alice has more streaks than Bob, return True, indicating Alice as the winner.\n     - Otherwise, return False, indicating Bob as the winner or a tie if counts are equal.\n\n\n\n# Complexity\n\n- Time Complexity: $$O(n)$$\n    - The time complexity of this code is O(n), where n is the length of the input \'colors\' string.\n    - The for loop iterates through the \'colors\' string, excluding the first and last characters, so the loop runs n-2 times (where n is the length of the `colors` string).\n    - Each iteration of the loop performs constant time operations (comparisons and increments), so the overall time complexity is linear in terms of the length of the \'colors\' string.\n\n\n- Space Complexity: $$O(1)$$\n    - The space complexity of this code is `O(1)`, which means it uses a constant amount of additional memory regardless of the input size.\n    \n    - The only variables that are used are `alice_count` and `bob_count`, which are integers and do not depend on the size of the input. Therefore, the space complexity is constant.\n\n```Python []\nclass Solution:\n    def winnerOfGame(self, colors: str) -> bool:\n        if len(colors) <= 2:\n            return False\n\n        alice_turn = 0\n        bob_turn = 0\n        \n        for i in range(1, len(colors) - 1):\n            if colors[i - 1] == colors[i] == colors[i + 1]:\n                if colors[i] == "A":\n                    alice_turn += 1\n                else:\n                    bob_turn += 1\n        \n        return alice_turn > bob_turn\n```\n```javascript []\n/**\n * @param {string} colors\n * @return {boolean}\n */\nvar winnerOfGame = function(colors) {\n    if (colors.length <= 2) {\n        return false;\n    }\n\n    let aliceTurn = 0;\n    let bobTurn = 0;\n\n    for (let i = 1; i < colors.length - 1; i++) {\n        if (colors[i - 1] === colors[i] && colors[i] === colors[i + 1]) {\n            if (colors[i] === \'A\') {\n                aliceTurn++;\n            } else {\n                bobTurn++;\n            }\n        }\n    }\n\n    return aliceTurn > bobTurn;    \n};\n```\n```java []\nclass Solution {\n    public boolean winnerOfGame(String colors) {\n        if (colors.length() <= 2) {\n            return false;\n        }\n\n        int aliceTurn = 0;\n        int bobTurn = 0;\n\n        for (int i = 1; i < colors.length() - 1; i++) {\n            if (colors.charAt(i - 1) == colors.charAt(i) && colors.charAt(i) == colors.charAt(i + 1)) {\n                if (colors.charAt(i) == \'A\') {\n                    aliceTurn++;\n                } else {\n                    bobTurn++;\n                }\n            }\n        }\n\n        return aliceTurn > bobTurn;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    bool winnerOfGame(string colors) {\n        if (colors.length() <= 2) {\n            return false;\n        }\n\n        int aliceTurn = 0;\n        int bobTurn = 0;\n\n        for (int i = 1; i < colors.length() - 1; i++) {\n            if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {\n                if (colors[i] == \'A\') {\n                    aliceTurn++;\n                } else {\n                    bobTurn++;\n                }\n            }\n        }\n\n        return aliceTurn > bobTurn;        \n    }\n};\n```\n\n\n---\n\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\nMy next post for daily coding challenge on October 3rd, 2023\nhttps://leetcode.com/problems/number-of-good-pairs/solutions/4122338/video-how-we-think-about-a-solution-python-javascript-java-c/
['C++', 'Java', 'Python3', 'JavaScript']