[Java/Python 3] three easy iterative codes w/ brief explanation, analysis and follow-up.
Method 1: ArrayDeque\n\nIf current char is same as previous char in the ArrayDeque, pop out the previous char; \nOtherwise, add current char into the ArrayDeque
**Method 1: ArrayDeque**\n\nIf current char is same as previous char in the ArrayDeque, pop out the previous char; \nOtherwise, add current char into the ArrayDeque.\n\n\n```\n    public String removeDuplicates(String S) {\n        Deque<Character> dq = new ArrayDeque<>();\n        for (char c : S.toCharArray()) {\n            if (!dq.isEmpty() && dq.peekLast() == c) { \n                dq.pollLast();\n            }else {\n                dq.offer(c);\n            }\n        }\n        StringBuilder sb = new StringBuilder();\n        for (char c : dq) { sb.append(c); }\n        return sb.toString();\n    }\n```\n```\n    def removeDuplicates(self, S: str) -> str:\n        dq = collections.deque()\n        for c in S:\n            if dq and dq[-1] == c:\n                dq.pop()\n            else:\n                dq.append(c)\n        return \'\'.join(dq)\n```\nOr just use list:\n```\n    def removeDuplicates(self, S: str) -> str:\n        stack = []\n        for c in S:\n            if stack and stack[-1] == c:\n                stack.pop()\n            else:\n                stack.append(c)\n        return \'\'.join(stack)\n```\n\n**Method 2: StringBuilder.**\n\nGet rid of the ArrayDeque in method 1, use only StringBuilder.\n\nIf current char is same as the end of the StringBuilder, delete the char at end; otherwise, append it at the end.\n\n```\n    public String removeDuplicates(String S) {\n        StringBuilder sb = new StringBuilder();\n        for (char c : S.toCharArray()) {\n            int size = sb.length();\n            if (size > 0 && sb.charAt(size - 1) == c) { \n                sb.deleteCharAt(size - 1); \n            }else { \n                sb.append(c); \n            }\n        }\n        return sb.toString();\n    }\n``` \n\n**Method 3: two pointers**\n\nIf current char is same as the end of non-adjacent-duplicate chars, decrease the counter `end` by 1;\notherwise, copy the current char to its end.\n\n```\n    public String removeDuplicates(String S) {\n        char[] a = S.toCharArray();\n        int end = -1;\n        for (char c : a) {\n            if (end >= 0 && a[end] == c) { \n                --end; \n            }else { \n                a[++end] = c; \n            }\n        }\n        return String.valueOf(a, 0, end + 1);\n    }\n```\n```\n    def removeDuplicates(self, S: str) -> str:\n        end, a = -1, list(S)\n        for c in a:\n            if end >= 0 and a[end] == c:\n                end -= 1\n            else:\n                end += 1\n                a[end] = c\n        return \'\'.join(a[: end + 1])\n```\n**Analysis for all methods:**\n\nTime & space: O(n), where n = S.length().\n\n----\n\n**Follow-up:**\n\nSee follow up [1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/discuss/393149/JavaPython-3-O(n)-codes-using-Stack-w-brief-explanation-and-analysis.)\n\nQ: What if we are required to **remove all k-in-a-row duplicates in a string (for more-than-k-in-a-row, remove only first k duplicates)**? - credit to **@betterztt**.\n\nA: Use 2 stacks, one for characters, and the other for the count of adjacent characters.\n\n```java\n    public String removeDuplicates(String S, int k) {\n        Deque<Character> charStk = new ArrayDeque<>();\n        Deque<Integer> cntStk = new ArrayDeque<>();\n        for (int i = 0; i < S.length(); ++i) {\n            char c = S.charAt(i);\n            if (charStk.isEmpty() || charStk.peek() != c) { // no char in stack yet, or top char is different from the current.\n                charStk.push(c);\n                cntStk.push(1);\n            }else if (cntStk.peek() + 1 < k) { // top char is same as the current, but less than k after appending the current.\n                cntStk.push(cntStk.pop() + 1);\n            }else { // found k-in-a-row duplicates, remove them.\n                charStk.pop();\n                cntStk.pop();\n            }\n        }\n        StringBuilder sb = new StringBuilder();\n        for (char c : charStk) {\n            int cnt = cntStk.pop();\n            while (cnt-- > 0) {\n                sb.append(c);\n            }\n        }\n        return sb.reverse().toString(); // Do NOT forget reverse().\n    }\n```\n```python\n    def removeDuplicates(self, S: str, k: int) -> str:\n         stk = []\n        for char in S:\n            if not stk or stk[-1][0] != char:\n                stk.append([char, 1])\n            elif stk[-1][1] + 1 < k:\n                stk[-1][1] += 1\n            else:\n                stk.pop()\n        return \'\'.join(char * cnt for char, cnt in stk)\n```\n
['Two Pointers', 'String', 'Iterator', 'Java']