给Jim一个字符串s(1<= s.length <= 104,s由小写英文字母组成),请Jim去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
时间: 2024-05-04 12:18:33 浏览: 12
可以使用栈来实现。遍历字符串,将字符依次压入栈中。对于每个字符,如果它已经在栈中出现过,则不做任何操作;否则,将它与栈顶元素比较,如果比栈顶元素小且栈顶元素在后面还有出现的机会,则弹出栈顶元素,直到栈顶元素比当前字符小或者不存在于后面的字符中,然后再将当前字符压入栈中。最后将栈中的元素弹出并逆序拼接即可。以下是示例代码:
```java
public static String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
int[] count = new int[26];
boolean[] visited = new boolean[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : s.toCharArray()) {
count[c - 'a']--;
if (visited[c - 'a']) {
continue;
}
while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] > 0) {
visited[stack.pop() - 'a'] = false;
}
stack.push(c);
visited[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
```