Welcome to my article! This artcle starts with "How we think about a solution". In other words, that is my thought process to solve the question. This article explains how I get to my solution instead of just posting solution codes or out of blue algorithms. I hope this aricle is helpful for someone.\n\n# Intuition\n\nUse stack to keep order of charcters in string with the smallest in lexicographical order.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/aU0MiLWAm4o\n\n\u25A0 Timeline of the video\n`0:00` Read the question of Remove Duplicate Letters\n`0:16` How we think about a solution - What is the smallest in lexicographical order for this question?\n`2:28` Demonstrate solution with an example.\n`7:43` Coding\n`10:00` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,493\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n\n# Approach\n\n## How we think about a solution\n\n### What is the smallest in lexicographical order for this quesiton?\nTo solve this question, we need to understand what smallest in lexicographical order is.\n\n```\nInput: "bcabc"\n```\n\nIn this case, we have duplicte characters `b` and `c`, so we need to remove one of `b` and one of `c`.\n\n```\n_ _ a b c \u2192 abc\n_ c a b _ \u2192 cab\nb _ a _ c \u2192 bac\nb c a _ _ \u2192 bca\n```\nWe can create 4 strings and need to keep order of appearance of each character. And then, sort the 4 strings lexicographically(alphabetically).\n```\nabc\nbac\nbca\ncab\n```\n\n`abc` is the smallest string, that\'s why we should return `abc`.\n\nThat is the smallest in lexicographical order we must understand for this question.\n\nNow, let\'s focus on \n```\n_(b) _(c) a b c \u2192 abc\n```\n From the idea above, we can say two important things.\n\n---\nWe want to put the smaller character in early position but we have to use big character(For example "z") if it is unique in the string.\n\n\nThe two important thing are as follows;\n1. Previous characters are lexicographically greater than current character\n2. The previous big characters show up again after position of current character\n\nIf both cases are true, we can remove the previous big charcters because we try to put smaller characters in early position and bigger characters in late position if possible. It leads to creating smaller string lexicographically and can remove duplicate characters.\n\n---\n\n\nIn this case, what data structure do you use? \n\nMy answer is to use `stack`. We want to compare current character with the last previous character one by one. We can use `pop` and `append` with `O(1)`. Seems like `stack` make the problem easy and efficient.\n\nLet\'s see one by one. First of all, `stack` is empty\n\n```\nstack = []\n```\nThe first character is `b` and `stack` is now empty, so just add `b` to `stack`\n```\nstack = ["b"]\n```\nThe next character is `c`, in this case, compare `c` with the last character in `stack` which is `b` with the main idea above.\n\n`c` is greater than `b`, so it\'s false case. Just add `c` in `stack`\n\n```\n"c" < "b" \u2192 false\nstack = ["b", "c"]\n```\n\nThe next character is `a`. Here is an interesting point. Compare `a` with the last character in `stack` which is `c`\n\n```\n"a" < "c" \u2192 true\nprevious character(c) will show up again after current position(a)? \u2192 true\n```\nIn that case, remove `c` from `stack`\n```\nstack = ["b"]\n```\nWe still have `b` in stack. Let\'s compare `a` vs `b`.\n```\n"a" < "b" \u2192 true\nprevious character(b) will show up again after current position(a)? \u2192 true\n```\nIn that case, remove `b` from `stack`. Now `stack` is empty. we stop comparing and add `a` to `stack`\n```\nstack = ["a"]\n```\nWe will repeat the same process. I\'ll speed up. The next character is `b`.\n```\n"b" < "a" \u2192 false\nstack = ["a", "b"]\n```\nThe next character is `c`.\n```\n"c" < "b" \u2192 false\nstack = ["a", "b", "c"]\n```\n\nAll we have to do is just to concatenate the characters remaining in the stack.\n\nThat is main point of how we think about a solution. Exepct the main idea, I use `Set` and `HashMap` to support the idea in the solution codes below. `Set` is used to prevent duplicate characters and `HashMap` is used to keep the last position of each character. I believe now you can understand them easily.\n\nLet\'s see a real algorithm!\n\n### Algorithm Overview\n1. Build a dictionary `last_occur` to store the last occurrence index of each character in the input string `s`.\n2. Iterate through the input string `s` to build the `last_occur` dictionary and initialize an empty stack and a visited set.\n3. Iterate through the characters in the input string `s` again. If a character is already visited, skip it. If not, process it based on certain conditions and update the stack and visited set accordingly.\n4. Finally, concatenate the characters remaining in the stack to get the final result.\n\n### Detailed Explanation\n1. Create a dictionary `last_occur` to store the last occurrence index of each character in the input string `s`.\n2. Iterate through each character and its index in the input string `s`:\n 1. Update the `last_occur` dictionary with the last occurrence index of the current character.\n3. Initialize an empty stack to hold the characters in the desired order and a visited set to keep track of visited characters.\n4. Iterate through each index `i` in the range of the length of the input string `s`:\n 1. Check if the current character `s[i]` is already visited. If visited, skip to the next iteration.\n 2. If the current character `s[i]` is not visited:\n 1. While the stack is not empty, the top of the stack is greater than `s[i]`, and the last occurrence of the top of the stack is after the current index `i`, remove the top of the stack and mark it as not visited.\n 2. Mark the current character `s[i]` as visited and push it onto the stack.\n5. Concatenate the characters remaining in the stack to obtain the final result.\n6. Return the concatenated string, which represents the characters in the desired order without duplicate letters.\n\n\n---\n\n\n\n# Complexity\nLet\'s analyze the time and space complexity of the given code.\n\n### Time Complexity:\nThe time complexity can be broken down as follows:\n\n1. **First Loop (iteration over string `s`):** This involves iterating over each character in string `s` to build the `last_occur` dictionary. This takes O(len(s)), where len(s) is the length of string `s`.\n\n2. **Second Loop (iteration over string `s`):** In the worst case, this loop iterates over each character in string `s` and performs operations such as stack manipulations and dictionary lookups, which are O(1) operations.\n\nHence, the overall time complexity is O(len(s)), where len(s) is the length of string `s`.\n\n### Space Complexity:\nThe space complexity is determined by the space used by the `last_occur` dictionary, the `stack`, and the `visited` set.\n\n1. **Dictionary (`last_occur`):** The space used by the `last_occur` dictionary is O(26) at most, considering only lowercase English letters, which is a constant.\n\n2. **Stack (`stack`):** In the worst case, the stack can contain all characters of string `s`. Therefore, the space used by the stack is O(len(s)), where len(s) is the length of string `s`.\n\n3. **Set (`visited`):** In the worst case, the visited set can contain all characters of string `s`. Therefore, the space used by the set is O(len(s)), where len(s) is the length of string `s`.\n\nHence, the overall space complexity of the code is O(max(len(s), 26)), which simplifies to O(len(s)) since 26 is a constant.\n\nBut regarding O(len(s)), we have also O(26) at most because we are not allowed to have duplicate characters, so we can say O(1) instead of O(len(s)).\n\n\n```python []\nclass Solution:\n def removeDuplicateLetters(self, s: str) -> str:\n # Dictionary to store the last occurrence of each character\n last_occur = {}\n\n # Record the last occurrence of each character\n for i, char in enumerate(s):\n last_occur[char] = i \n\n stack = [] # Stack to store characters in the desired order\n visited = set() # Set to keep track of visited characters\n\n for i in range(len(s)):\n if s[i] in visited:\n continue # Skip if the character is already visited\n\n # If the top of the stack is greater than s[i] and will occur later again, remove from stack\n while stack and s[i] < stack[-1] and i < last_occur.get(stack[-1], -1):\n visited.remove(stack.pop())\n\n visited.add(s[i]) # Mark as visited\n stack.append(s[i]) # Add to the stack\n \n return \'\'.join(stack) # Concatenate the characters remaining in the stack\n\n```\n```javascript []\n/**\n * @param {string} s\n * @return {string}\n */\nvar removeDuplicateLetters = function(s) {\n const lastOccurrence = {};\n for (let i = 0; i < s.length; i++) {\n lastOccurrence[s[i]] = i;\n }\n\n const stack = [];\n const visited = new Set();\n\n for (let i = 0; i < s.length; i++) {\n if (visited.has(s[i])) {\n continue;\n }\n\n while (\n stack.length > 0 &&\n s[i] < stack[stack.length - 1] &&\n i < lastOccurrence[stack[stack.length - 1]]\n ) {\n visited.delete(stack.pop());\n }\n\n visited.add(s[i]);\n stack.push(s[i]);\n }\n\n return stack.join(\'\'); \n};\n```\n```java []\nclass Solution {\n public String removeDuplicateLetters(String s) {\n Map lastOccurrence = new HashMap<>();\n for (int i = 0; i < s.length(); i++) {\n lastOccurrence.put(s.charAt(i), i);\n }\n\n Stack stack = new Stack<>();\n Set visited = new HashSet<>();\n\n for (int i = 0; i < s.length(); i++) {\n if (visited.contains(s.charAt(i))) {\n continue;\n }\n\n while (!stack.isEmpty() && s.charAt(i) < stack.peek() && i < lastOccurrence.getOrDefault(stack.peek(), -1)) {\n visited.remove(stack.pop());\n }\n\n visited.add(s.charAt(i));\n stack.push(s.charAt(i));\n }\n\n StringBuilder result = new StringBuilder();\n for (char ch : stack) {\n result.append(ch);\n }\n return result.toString(); \n }\n}\n```\n```C++ []\nclass Solution {\npublic:\n string removeDuplicateLetters(string s) {\n std::unordered_map lastOccurrence;\n for (int i = 0; i < s.length(); i++) {\n lastOccurrence[s[i]] = i;\n }\n\n std::stack stack;\n std::unordered_set visited;\n\n for (int i = 0; i < s.length(); i++) {\n if (visited.find(s[i]) != visited.end()) {\n continue;\n }\n\n while (!stack.empty() && s[i] < stack.top() && i < lastOccurrence[stack.top()]) {\n visited.erase(stack.top());\n stack.pop();\n }\n\n visited.insert(s[i]);\n stack.push(s[i]);\n }\n\n std::string result;\n while (!stack.empty()) {\n result = stack.top() + result;\n stack.pop();\n }\n return result; \n }\n};\n```\n\n\n---\n\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\nMy next post for daily coding challenge on Sep 27th, 2023\nhttps://leetcode.com/problems/decoded-string-at-index/solutions/4096860/how-i-think-about-a-solution-python-java-c/

Remove Duplicate Letters

Problem Description

Problem Description

Answer Panel