316. Remove Duplicate Letters

  • 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
2
3
4
5
6
Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

方法一:

代码中有bug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
string removeDuplicateLetters(string s) {
string res = "";
unordered_map<char, int> map;
int n = s.size();
for(int i=0; i<n; i++)
map[s[i]] = i;
int i=0, j, k, l;
while(i<n && map.size()){
char c = s[i];
j = min_index(map);
for(k=i+1; k<=j; k++){
if(s[k]<s[i]){
l = k;
c = s[k];
}
}
res += c;
map.erase(c);
i = l+1;
}
return res;
}

int min_index(unordered_map<char, int>& map){
int index = map.size();
for(auto it=map.begin(); it!=map.end(); it++)
index = min(index, it->second);
return index;
}
};

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”:

  1. find out the last appeared position for each letter;
    c - 7
    b - 6
    a - 2
    d - 4
  2. find out the smallest index from the map in step 1 (a - 2);
  3. the first letter in the final result must be the smallest letter from index 0 to index 2;
  4. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {

public String removeDuplicateLetters(String s) {
if (s == null || s.length() <= 1) return s;

Map<Character, Integer> lastPosMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastPosMap.put(s.charAt(i), i);
}

char[] result = new char[lastPosMap.size()];
int begin = 0, end = findMinLastPos(lastPosMap);

for (int i = 0; i < result.length; i++) {
char minChar = 'z' + 1;
for (int k = begin; k <= end; k++) {
if (lastPosMap.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
minChar = s.charAt(k);
begin = k+1;
}
}

result[i] = minChar;
if (i == result.length-1) break;

lastPosMap.remove(minChar);
if (s.charAt(end) == minChar) end = findMinLastPos(lastPosMap);
}

return new String(result);
}

private int findMinLastPos(Map<Character, Integer> lastPosMap) {
if (lastPosMap == null || lastPosMap.isEmpty()) return -1;
int minLastPos = Integer.MAX_VALUE;
for (int lastPos : lastPosMap.values()) {
minLastPos = Math.min(minLastPos, lastPos);
}
return minLastPos;
}

}


cpp


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

C++ simple solution easy understanding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string removeDuplicateLetters(string s) {
vector<int> cand(256, 0);
vector<bool> visited(256, false);
for (char c : s)
cand[c]++;
string result = "0";
for (char c : s) {
cand[c]--;
if (visited[c]) continue;
while (c < result.back() && cand[result.back()]) {
visited[result.back()] = false;
result.pop_back();
}
result += c;
visited[c] = true;
}
return result.substr(1);
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> dict(256, 0);
vector<bool> visited(256, false);
for(auto ch : s) dict[ch]++;
string result = "0";
/** the key idea is to keep a monotically increasing sequence **/
for(auto c : s) {
dict[c]--;
/** to filter the previously visited elements **/
if(visited[c]) continue;
while(c < result.back() && dict[result.back()]) {
visited[result.back()] = false;
result.pop_back();
}
result += c;
visited[c] = true;
}
return result.substr(1);
}
};

https://discuss.leetcode.com/topic/31436/short-16ms-o-n-c-solution-using-stack-which-can-be-optimized-down-to-4ms

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
string removeDuplicateLetters(string s) {
unordered_map<char, int> cnts;
string ret;
stack<char> stk;
vector<bool> isVisited(26, false);
for (char each : s) cnts[each] ++;
for (int i = 0; i < s.size(); cnts[s[i]] --, ++ i) {
if (isVisited[s[i] - 'a'] || (!stk.empty() && stk.top() == s[i])) continue;
while (!stk.empty() && stk.top() > s[i] && cnts[stk.top()] > 0) {
isVisited[stk.top() - 'a'] = false;
stk.pop();
}
stk.push(s[i]);
isVisited[s[i] - 'a'] = true;
}
while (!stk.empty()) {
ret.push_back(stk.top());
stk.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};

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
2
3
4
5
6
def removeDuplicateLetters(self, s):
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(suffix) == set(s):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''

Solution 2

Inspired by WHJ425’s explanation.

1
2
3
4
5
6
7
8
def removeDuplicateLetters(self, s):
result = ''
while s:
i = min(map(s.rindex, set(s)))
c = min(s[:i+1])
result += c
s = s[s.index(c):].replace(c, '')
return result

Solution 3

Inspired by halibut735’s solution.

1
2
3
4
5
6
7
8
9
def removeDuplicateLetters(self, s):
rindex = {c: i for i, c in enumerate(s)}
result = ''
for i, c in enumerate(s):
if c not in result:
while c < result[-1:] and i < rindex[result[-1]]:
result = result[:-1]
result += c
return result

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

  1. removing all letters to the left of s[i],
  2. 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
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
int pos = 0; // the position for the smallest s[i]
for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos)) pos = i;
if (--cnt[s.charAt(i) - 'a'] == 0) break;
}
return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
}
}

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

Java solution using Stack with comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public String removeDuplicateLetters(String sr) {

int[] res = new int[26]; //will contain number of occurences of character (i+'a')
boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
char[] ch = sr.toCharArray();
for(char c: ch){ //count number of occurences of character
res[c-'a']++;
}
Stack<Character> st = new Stack<>(); // answer stack
int index;
for(char s:ch){
index= s-'a';
res[index]--; //decrement number of characters remaining in the string to be analysed
if(visited[index]) //if character is already present in stack, dont bother
continue;
//if current character is smaller than last character in stack which occurs later in the string again
//it can be removed and added later e.g stack = bc remaining string abc then a can pop b and then c
while(!st.isEmpty() && s<st.peek() && res[st.peek()-'a']!=0){
visited[st.pop()-'a']=false;
}
st.push(s); //add current character and mark it as visited
visited[index]=true;
}

StringBuilder sb = new StringBuilder();
//pop character from stack and build answer string from back
while(!st.isEmpty()){
sb.insert(0,st.pop());
}
return sb.toString();
}

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

15 ms Java solution

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

1
2
3
4
a----2
b----1,6
c----0,3,5,7
d----4

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
2
3
b----6
c----3,5,7
d----4

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
2
b---6
d---4

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
public String removeDuplicateLetters(String s) {
HashMap<Character, ArrayList<Integer>> counts = new HashMap<Character, ArrayList<Integer>>();
ArrayList<Character> keys = new ArrayList<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!counts.containsKey(c)) {
counts.put(c, new ArrayList<Integer>());
keys.add(c);
}
counts.get(c).add(i);
}
Collections.sort(keys);
StringBuilder sb = new StringBuilder();
while (!counts.isEmpty()) {
boolean found = true;
for (int i = 0; i < keys.size(); i++) {
int index = counts.get(keys.get(i)).get(0);
for (int j = 0; j < keys.size(); j++) {
ArrayList<Integer> count = counts.get(keys.get(j));
if (count.get(count.size() - 1) < index) {
found = false;
break;
}
}
if (found) {
sb.append(keys.get(i));
counts.remove(keys.get(i));
keys.remove(i);
for (int j = 0; j < keys.size(); j++) {
ArrayList<Integer> count = counts.get(keys.get(j));
while (count.get(0) < index) {
count.remove(0);
}
}
break;
}
found = true;
}
}
return sb.toString();
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
int[] count = new int[26];
char[] arr = s.toCharArray();
for(char c : arr) {
count[c-'a']++;
}
boolean[] visited = new boolean[26];
for(char c : arr) {
count[c-'a']--;
if(visited[c-'a']) {
continue;
}
while(!stack.isEmpty() && stack.peek() > c && count[stack.peek()-'a'] > 0) {
visited[stack.peek()-'a'] = false;
stack.pop();
}
stack.push(c);
visited[c-'a'] = true;
}
StringBuilder sb = new StringBuilder();
for(char c : stack) {
sb.append(c);
}
return sb.toString();
}
谢谢你,可爱的朋友。