[python3] Stack approach O(n) Candy crush :)
Think about this as Candy Crush for a single row where you can only crush two candies at a time :) The idea is to have a stack to store the visited chars. If th
Think about this as Candy Crush for a single row where you can only crush two candies at a time :) The idea is to have a stack to store the visited chars. If the current char in the string is the same as the last char in the stack, pop the last char from the stack and skip the current char in the string; otherwise, append the current char to the stack.\n\n```\nclass Solution:\n    def removeDuplicates(self, s: str) -> str:\n    \t### initialize an empty stack\n        stack = []\n\n        for char in s:\n        \t\n        \t### This is the case where two adjacent letters are equal\n        \t### don\'t store it and pop the last one from stack,\n        \t### Don\'t forget to check if the stack is empty!\n            if stack and char==stack[-1]:\n                stack.pop()\n\n            else:\n                stack.append(char)\n        \n        return \'\'.join(stack)\n```\n\n**Time complexity** is **O(n)** since we just went over ```s```.\n\nRuning the code with an example ```s = "abbaca"```\n```\n\t\t\t\tBEFORE\t\t\t\t\t\t\t\t\t\t\t\t\tAFTER\n\ti=0\t\t\tstack=[]\t\ts[i]=a \t\tempty stack, append\t\t\tstack=[a]\n\ti=1\t\t\tstack=[a]\t\ts[i]=b \t\tstack[-1]!=s[i], append\t\tstack=[a,b]\n\ti=2\t\t\tstack=[a,b]\t\ts[i]=b \t\tstack[-1]==s[i], pop\t\tstack=[a]\n\ti=3\t\t\tstack=[a]\t\ts[i]=a \t\tstack[-1]==s[i], pop\t\tstack=[]\n\ti=4\t\t\tstack=[]\t\ts[i]=c \t\tstack[-1]!=s[i], append\t\tstack=[c]\n\ti=5\t\t\tstack=[c]\t\ts[i]=a \t\tstack[-1]!=s[i], append\t\tstack=[c,a] (result)\n```\n\nOne line from genius [lee215](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/discuss/294893/JavaC%2B%2BPython-Two-Pointers-and-Stack-Solution):\n\n```python\nclass Solution:\n    def removeDuplicates(self, s):\n        return reduce(lambda stack, char: stack[:-1] if stack[-1:] == char else stack + char, s)\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]