(With diagrams) Java Implictly Stack solution beats 99.7% time and 97.6% space
For this dedup problem, first let us think about if we don\'t use computer, just do it by hand. We will scan from left to right to see whether we need to de-dup
For this dedup problem, first let us think about if we don\'t use computer, just do it by hand. We will scan from left to right to see whether we need to de-duplicates. It required us to look back to previous step and check whether the character we added is the same as current character.\n\nThus it is easier to think out to use Stack to handle this case. Thus there will be two ways:\n* Explicitly maintian a stack: `ArrayDeque<Character>` or `LinkedList<Character>`\n* Implicitly simulate a stack: Two pointers or StringBuilder\n\nHere I will use Two Pointers to simulate a stack to be more efficient:\n* Slow: represent the last elemetn to be returned, initialize as 0\n* Fast: traverse the whole char array\n```Java\nclass Solution {\n    public String removeDuplicates(String S) {\n        if (S == null || S.length() <= 1) {\n            return S;\n        }\n        char[] chars = S.toCharArray(); // maintain as stack\n        int slow = 0; // slow is the last element to be returned\n        // [0, slow] will be the result after removing (inclusive)\n        \n        for (int fast = 1; fast < S.length(); fast++) {\n            if (slow >= 0 && chars[slow] == chars[fast]) { // case 1: stack top has same data\n                slow--; // stack.pop()\n            } else { // case 2: stack top is different\n                chars[++slow] = chars[fast]; // stack.push()\n            }\n        }\n        return new String(chars, 0, slow + 1);\n    }\n}\n```\nLet\'s use one example to see what is going on here:\n```\ninitially fast = 1, slow = 0\n\ta b b a c a\n\ts \u2192\n\t  f \u2192\n---------------------------------------------------\nchars[fast] != chars[slow], s++, copy chars[fast] to slow, f++ (same as stack.push())\n\ta b b a c a\n\t  s \u2192\n\t    f \u2192\n---------------------------------------------------\nchars[fast] == chars[slow], f++, s-- (same as stack.pop())\n\ta b b a c a\n\ts \u2192\n\t      f \u2192\n---------------------------------------------------\nchars[fast] == chars[slow], f++, s-- (same as stack.pop())\n\ta b b a c a\n  s \u2192\n\t        f \u2192\n---------------------------------------------------\nchars[fast] != chars[slow], s++, copy chars[fast] to slow, f++ (same as stack.push())\n\tc b b a c a\n    s \u2192\n\t          f \u2192 \n---------------------------------------------------\nchars[fast] != chars[slow], s++, copy chars[fast] to slow, f++ (same as stack.push())\n\tc a b a c a\n      s \u2192\n\t            f \u2192 \n---------------------------------------------------\nDone! \'ca\' will be returned.\n```
['Two Pointers', 'Java']