Java, double ended queue, no stack, explained, 7ms
For this task we can use stack and analyse last seen char with current. But this approach has one tradeoff - added chars are in reverse order so we need to reve
For this task we can use stack and analyse last seen char with current. But this approach has one tradeoff - added chars are in reverse order so we need to reverse it at the end. To avoid this we can use double ended queue - add chars at the end, but read it from the head for the final string.\nThis leads to solution below.\nO(n) time and space - read ever char 2 times when checking for duplicates and then form result string. Also we need O(n) space for the deque.\n\n```\n    public String removeDuplicates(String S) {\n        Deque<Character> deq = new LinkedList();\n        //iterate over the chars in string\n        for (char ch : S.toCharArray()) {\n            //check if the last char we checked is equal to the current one\n            //if so - don\'t add current and remove that previosuly added\n            //else add char to the stack\n            if (!deq.isEmpty() && deq.peekLast() == ch) {\n                deq.pollLast();\n            } else {\n                deq.addLast(ch);\n            }\n        }\n        //form the result string by polling from the stack in reversed order\n        char[] strArr = new char[deq.size()];\n        for (int i = 0; i < strArr.length; i++) {\n            strArr[i] = deq.pollFirst();\n        }  \n        return new String(strArr);\n    }\n```
['Queue', 'Java']