My code:
public class Solution {
public String removeDuplicateLetters(String s) {
if (s == null || s.length() == 0)
return s;
int len = s.length();
Stack<Character> tracker = new Stack<Character>();
HashMap<Character, Integer> dic = new HashMap<Character, Integer>(); // character -> numbers of this character
/** form this dictionary to record the numbers of characters */
for (int i = 0; i < len; i++) {
char curr = s.charAt(i);
if (!dic.containsKey(curr))
dic.put(curr, 1);
else {
int times = dic.get(curr);
dic.put(curr, times + 1);
}
}
/** remove elements from string */
for (int i = 0; i < len; i++) {
char curr = s.charAt(i);
if (tracker.isEmpty())
tracker.push(curr);
else if (tracker.contains(curr)) {
int times = dic.get(curr);
dic.put(curr, times - 1);
continue;
}
else {
while (!tracker.isEmpty()) {
int times = dic.get(tracker.peek());
if (curr < tracker.peek() && times > 1) {
dic.put(tracker.peek(), times - 1);
tracker.pop();
}
else {
tracker.push(curr);
break;
}
}
if (tracker.isEmpty())
tracker.push(curr);
}
}
StringBuilder ret = new StringBuilder();
while (!tracker.isEmpty()) {
ret.append(tracker.pop());
}
return ret.reverse().toString(); // string does not have reverse() method
}
}
这道题木我没有做出来。看了答案才想出来。
一开始我写了我的解法，就是看右边的值是否比自己小。小的化就删除自己。后来发现，右边第一个可能比自己大，但是右边第二个比自己小的时候，依然得把自己删除。然后我就不知道怎么继续写了。看了答案。拿Stack来做。很巧妙。
首先，为什么拿Stack来做呢？他的什么特性复合这道题木呢？
我们需要拿后面的字母和前面的作比较，进行操作，而不需要拿前面的字母和后面的字母作比较。所以，栈很合适。
做法是，先用HashMap做一个字典。统计每个字母出现的个数。
然后遍历整个字符串。
当栈为空的时候，直接插入。
非空时，
当插入的元素，栈中已经存在了，那么就舍弃，直接continue；
当插入的元素，比栈顶元素值要小时，判断该栈顶元素的对应counter是否大于1，如果大于1，说明以后还会出现。那么，就把该元素pop出来。然后拿插入元素和新的栈顶元素比较，进行相同操作。直到最后栈空或者栈顶元素小于该插入元素时，就向栈插入该元素。
这一步很关键，他保证了，栈中的元素，从底部到顶部，值是从小到大的。除非某些元素一共只出现了一次，那没办法。
然后新的插入元素出现时，如果栈顶元素，即他左侧的字母，是可以删除的（counter > 1）， 那么我们就该选择删除这个元素而不是后面的，因为这样的话，值小的元素就能移动到前端，满足字符顺序。
如果插入元素已经存在在了栈中，那么丢弃该元素，也就是删除该字母而不是前面的相同字母。为什么。因为栈是从大到小排列的，此刻的字符串，字母是从小到大的。删除了栈中的元素，会使得字典顺序变大。
还有一种解法具体我就不研究了。
参考网页：
https://www.hrwhisper.me/leetcode-remove-duplicate-letters/
Anyway, Good luck, Richardo!
My code:
import java.util.HashMap;
public class Solution {
public String removeDuplicateLetters(String s) {
if (s == null || s.length() == 0) {
return s;
}
HashMap<Character, Integer> helper = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
helper.put(curr, i);
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
StringBuilder ret = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (!map.containsKey(curr)) {
ret.append(curr);
map.put(curr, ret.length() - 1);
}
else {
int pre = map.get(curr);
int start = -1;
int end = pre + 1;
while (end < ret.length()) {
if (ret.charAt(end) > ret.charAt(pre)) {
if (find(s, i + 1, ret.charAt(end), helper)) {
end++;
}
else {
break;
}
}
else {
if (start == -1 || ret.charAt(start) > ret.charAt(end)) {
start = end;
}
if (find(s, i + 1, ret.charAt(end), helper)) {
end++;
}
else {
break;
}
}
}
if (start != -1) {
StringBuilder temp = new StringBuilder(ret.substring(0, pre));
map.clear();
for (int j = 0; j < pre; j++) {
map.put(ret.charAt(j), j);
}
for (int j = start; j < ret.length(); j++) {
temp.append(ret.charAt(j));
map.put(ret.charAt(j), temp.length() - 1);
}
temp.append(curr);
map.put(curr, temp.length() - 1);
ret = temp;
}
}
}
return ret.toString();
}
private boolean find(String s, int start, char target, HashMap<Character, Integer> helper) {
return helper.get(target) >= start;
}
public static void main(String[] args) {
Solution test = new Solution();
String ret = test.removeDuplicateLetters("mitnlruhznjfyzmtmfnstsxwktxlboxutbic");
System.out.println(ret);
}
}
没想到之前做过这道题目，可我完全没印象了。。。
然后自己写了出来，提交了好多次。。。许多细节问题没能考虑到。
先说下我的思想。其实也是栈的思想，思路起源于这道题目：
http://www.jianshu.com/p/d6115154c548
他其中的一个子问题，给定 arr[], k, 取出k个数字组成最大的数字，保留原数组顺序。
然后这道题目很像，就是当碰到某些条件需要删除时，什么情况下，可以删除。什么情况下，不能删除。
首先，条件是什么？
条件是，当当前这个字符，在之前已经出现过了。
ok,然后我们就需要考虑，删不删？
我们取出原字符的index，从他后面开始遍历。
这里有个细节，遍历的是之前扫出来的独一无二的string, ret
int pre = map.get(curr);
so end = pre + 1;
while (end < ret.length()) {
....
}
然后对于遍历的每个字符
if (ret.charAt(curr) > ret.charAt(pre)) {
...
}
else {
...
}
如果大的话，这个字符肯定不能删，但不代表后面不会出现更小的。
那么我们就需要判断，这个较大的字符，如果删了，后面有没有补充。
即，在 s[i + 1, s.length() - 1] 的范围内，该较大的字符是否仍然存在。
如果是，那么，那么就往后继续走，看看有没有小的。
如果不是，直接跳出循环。
如果小的话，我们需要考虑 start 的赋值。
如果start == -1, 那么直接赋值。
如果start != -1, 那么，如果当前的字符，同样小于原start指向的字符，那么就更新start，否则，就略过。
然后接着判断，是否可以继续扫下去。原理差不多。
然后就差不多了。
然后看了下以前的解法，用Stack的。真的很简洁！
自己重写了下：
My code:
public class Solution {
public String removeDuplicateLetters(String s) {
if (s == null || s.length() == 0) {
return s;
}
HashMap<Character, Integer> dic = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (!dic.containsKey(curr)) {
dic.put(curr, 1);
}
else {
dic.put(curr, dic.get(curr) + 1);
}
}
Stack<Character> st = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
dic.put(curr, dic.get(curr) - 1);
if (st.isEmpty()) {
st.push(curr);
}
else if (st.contains(curr)) {
continue;
}
else {
if (curr > st.peek()) {
st.push(curr);
}
else {
while (!st.isEmpty() && st.peek() > curr && dic.get(st.peek()) > 0) {
st.pop();
}
st.push(curr);
}
}
}
StringBuilder ret = new StringBuilder();
while (!st.isEmpty()) {
ret = ret.append(st.pop());
}
return ret.reverse().toString();
}
}
Anyway, Good luck, Richardo! -- 08/25/20
