Detailed explanation of logic with code
The lexicographic part is the trouble maker in an otherwise simple problem.\nWe don\'t just want to remove the duplicates, but we want to remove duplicates in a
The lexicographic part is the trouble maker in an otherwise simple problem.\nWe don\'t just want to remove the duplicates, but we want to remove duplicates in a manner that the resultant string is lexicographically smallest.\n\nLet\'s try to get to the solution using an example.\n\ns = "bcabc"\nHere we have 4 possible solutions: abc, bca, bac, cab. Out of these abc is smallest lexicographically.\n\n**Observations:**\n\n* We need a mechanism to know whether a certain character is going to appear later in the string. In our above example, At index 0, we have b. But we need to know whether b will appear again or not. If it appears again, then we can think of removing it. But if it does not appear again, then we have no choice but to keep this letter in our answer.\n* If current letter is lexicographically smaller than previous letters, AND the previous letters appear again later in array, we need to remove these previous letters from our answer, and add the current letter. Which data structure is best for keeping track of previous consecutive data? Stack!\n\n**Approach:**\n* To keep track of the highest index of each letter, we will use a Hashmap. So once we will go through the string and update our map. key will be the character, and value will be its index. Once the traversal is done, all characters will have highest indices updated in the map. (See first 5 lines code for clarity.)\n* We will use a stack to keep track of the letters, but we will also need a mechanism for checking whether a letter has already been added to the stack. (This point will become clear in a while)\n* We now go through the string, and do the following for each letter:\n1. Check if this letter is lexicographically smaller/bigger than the character at the top of the stack. If it is smaller, then we will **pop the stack only if the character at the top appears again later in the string**. Other wise just add it to the stack and the set iff this letter is not already added earlier (This is where the set comes in handy).\n2. Repeat the above step as long as current character is smaller than stack\'s top character.\n3. If the current character is bigger, then simply add this character to the stack and set if not already added before.\nGo through the code for better clarity.\n\nCode:\n```\nclass Solution {\n    public String removeDuplicateLetters(String s) {\n        HashMap<Character, Integer> countMap = new HashMap();\n        for(int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            countMap.put(c,i);\n        }\n        \n        Stack<Character> stack = new Stack();\n        Set<Character> set = new HashSet();\n        \n        for(int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if(!set.contains(c)) {\n                while(!stack.isEmpty() \n                      && c < stack.peek() \n                      && countMap.get(stack.peek()) >= i){\n                    set.remove(stack.pop());\n                }\n                stack.push(c);\n                set.add(c);\n            }\n        }\n        \n        String ans = "";\n        while(!stack.isEmpty()) {\n            ans = stack.pop() + ans;\n        }\n        \n        return ans;\n    }\n}\n```\n\n\nHope this helps.\nPlease drop comments for any queries/suggestions.\nPeace!
['Stack']