- 29.6%

https://leetcode.com/problems/remove-duplicate-letters/

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

1 | Example: |

方法一:

代码中有bug

1 | class Solution { |

https://discuss.leetcode.com/topic/31413/easy-to-understand-iterative-java-solution

The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input “cbacdcbc”:

- find out the last appeared position for each letter;

c - 7

b - 6

a - 2

d - 4 - find out the smallest index from the map in step 1 (a - 2);
- the first letter in the final result must be the smallest letter from index 0 to index 2;
- repeat step 2 to 3 to find out remaining letters.

- the smallest letter from index 0 to index 2: a
- the smallest letter from index 3 to index 4: c
- the smallest letter from index 4 to index 4: d
- the smallest letter from index 5 to index 6: b

so the result is “acdb”

Notes:

after one letter is determined in step 3, it need to be removed from the “last appeared position map”, and the same letter should be ignored in the following steps

in step 3, the beginning index of the search range should be the index of previous determined letter plus one

1 | public class Solution { |

#### cpp

https://discuss.leetcode.com/topic/32172/c-simple-solution-easy-understanding

C++ simple solution easy understanding

1 | string removeDuplicateLetters(string s) { |

I think this solution is really concise! But I want to add some detailed explainations to show why we do so to solve the problem, This problem is in fact similiar to the problem “Largest Rectangle under the histogram “

We need to keep the monotically decreasing substring that contains all the char in the s. So we just use a vector to mimic the stack! Just similiar to the previous many solutions that use the vector to simulate a stack.

In fact this problem is also similiar to the problem that the maximum in the sliding windows, I strongly recommend you to grasp the sliding windows solutions.

Here is the AC C++ implementation

1 | class Solution { |

Short 16ms O(n) c++ solution using stack which can be optimized down to 4ms

1 | class Solution { |

#### python

https://discuss.leetcode.com/topic/31561/some-python-solutions

Some Python solutions

Solutions inspired by those of others. Simpler but less efficient (all still get accepted, of course, in about 50 to 100 ms, normal for Python).

Solution 1

Inspired by lixx2100’s explanation.

1 | def removeDuplicateLetters(self, s): |

Solution 2

Inspired by WHJ425’s explanation.

1 | def removeDuplicateLetters(self, s): |

Solution 3

Inspired by halibut735’s solution.

1 | def removeDuplicateLetters(self, s): |

#### java

https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution

Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t.

the suffix s[i .. ] contains all the unique letters. (Note that, when there are more than one smallest s[i]’s, we choose the leftmost one. Why? Simply consider the example: “abcacb”.)

After determining the greedy choice s[i], we get a new string s’ from s by

- removing all letters to the left of s[i],
- removing all s[i]’s from s.

We then recursively solve the problem w.r.t. s’.

The runtime is O(26 * n) = O(n).

1 | public class Solution { |

https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments

Java solution using Stack with comments

1 | public String removeDuplicateLetters(String sr) { |

https://discuss.leetcode.com/topic/31424/15-ms-java-solution

15 ms Java solution

for “cbacdcbc”, we counts each letter’s index:

1 | a----2 |

we go from a to d, to find the first letter who has a index smaller than the largest index of the rest. Here, index 2 of letter a is smaller than 6, 7, 4, so we first pick a; then we remove all index smaller than 2, and we have:

1 | b----6 |

the next round we pick c not b, why ? cuz 6 of b is larger than 4, but 3 of c is smaller than 4 and 6.

1 | b---6 |

then we pick d and b to form “acdb”

O(n) time to count index, and as we only have 26 letters, it’s about O(26 * 26) to find a candidate letter and O(n) time to remove all index. So I think the running time is O(n).

1 | public class Solution { |

https://discuss.leetcode.com/topic/43469/java-o-n-solution-using-stack-with-detail-explanation

Java O(n) solution using stack with detail explanation

First, given “bcabc”, the solution should be “abc”. If we think about this problem intuitively, you would sort of go from the beginning of the string and start removing one if there is still the same character left and a smaller character is after it. Given “bcabc”, when you see a ‘b’, keep it and continue with the search, then keep the following ‘c’, then we see an ‘a’. Now we get a chance to get a smaller lexi order, you can check if after ‘a’, there is still ‘b’ and ‘c’ or not. We indeed have them and “abc” will be our result.

Come to the implementation, we need some data structure to store the previous characters ‘b’ and ‘c’, and we need to compare the current character with previous saved ones, and if there are multiple same characters, we prefer left ones. This calls for a stack.

After we decided to use stack, the implementation becomes clearer. From the intuition, we know that we need to know if there are still remaining characters left or not. So we need to iterate the array and save how many each characters are there. A visited array is also required since we want unique character in the solution. The line while(!stack.isEmpty() && stack.peek() > c && count[stack.peek()-‘a’] > 0) checks that the queued character should be removed or not, like the ‘b’ and ‘c’ in the previous example. After removing the previous characters, push in the new char and mark the visited array.

Time complexity: O(n), n is the number of chars in string.

Space complexity: O(n) worst case.

1 | public String removeDuplicateLetters(String s) { |