KK's blog

每天积累多一些

0%

LeetCode 316 Remove Duplicate Letters

Posted on Edited on Disqus:

LeetCode 316 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.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

题目大意：

给定一个只包含小写字母的字符串，从中移除重复字母使得每个字母只出现一次。你必须确保结果的字典序最小。

解题思路：

这题是保持原顺序输出结果，所以考虑用递减栈(递增栈，从栈底递增，求最小即用递增，如求k个最大用最小堆一样)。先看例子bcabc->abc，a入栈倒逼
bc出栈，可解此题。因为既然bc在栈外还有，就可以出栈，保证第一个字母最小（题目要求）。再看cbacdcbc，acd时候b入栈，不能倒逼cd出栈
因为d是唯一一个，所以还要维护一个hashMap来记录每个字母的词频。所以入栈条件为准入栈元素小于栈顶元素且栈顶元素为最后一个（频数>0）。
hashMap作用有两个，第一个为统计词频，第二个为记录未入栈的字母的频数。
resultSet记录stack中所有唯一元素，用于判断是否需要入栈。这是难点，对于已在栈中的重复元素不需要再入栈，因为它在栈中的位置已经是目前
最小的位置，如果要出现更小的结果只能通过非栈内元素倒逼产生新结果。如acabc，第二个a不需要逼c出来，b可以做到这一点，a已在最小位置。

注意事项：

  1. 已在栈内的重复元素不入栈，也不倒逼任何元素出栈，也就是直接忽略它，只要将其频数减一即可，表示已处理。比如abacb，第二个a不能倒逼b。用两个数据结构：set保证不重复加入到栈内，map保证外面还有元素可入栈
  2. 进入循环后频数立刻减一，不要出列时候才做，参见BFS。
  3. 出栈条件：栈不为空，准入栈元素小于栈顶元素，栈顶元素频数>0（表示栈外还有元素可以入栈）。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeDuplicateLetters(self, s: str) -> str:
	char_to_count = collections.Counter(s)
	stack, stack_set = [], set()
	for i in range(len(s)):
		char_to_count[s[i]] -= 1
		if s[i] in stack_set:
			continue
		while stack and s[i] < stack[-1] and char_to_count[stack[-1]] > 0:
			stack_set.remove(stack[-1])
			stack.pop()
		stack.append(s[i])
		stack_set.add(s[i])
	return ''.join(stack)

Java代码：

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
public String removeDuplicateLetters(String s) {
	Stack<Character> stack = new Stack<Character>();
	Map<Character, Integer> map = new HashMap<Character, Integer>();
	Set<Character> result = new HashSet<Character>();
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		if(map.containsKey(c))
			map.put(c, map.get(c)+1);
		else
			map.put(c, 1);
	}
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		map.put(c, map.get(c)-1);
		
		//Stack已经有c就不加入
		if(result.contains(c))
			continue;
		
		while(!stack.isEmpty() && c<stack.peek() && map.get(stack.peek())>0){
			result.remove(stack.peek());
			stack.pop();
		}
		stack.push(c);
		result.add(c);
	}
	
	StringBuilder sb = new StringBuilder();
	while(!stack.isEmpty())
		sb.append(stack.pop());
	return sb.reverse().toString();  	
}

算法分析：

所有元素入栈出栈最多一次，所以时间复杂度为O(n)，空间复杂度O(n)。

Free mock interview