Leetcode316. Remove Duplicate Le

问题描述

给定一个字符串，移除重复的字符使得最后所得字符串字典顺序最小

Example

Input: "bcabc"
Output: "abc"

分析

这题在leetcode中属于一道hard题，是一道经典的贪婪算法题型。给定一个字符串，移除重复的字符，使得字典顺序最小，则要求我们保证较小的字符一定最先出现在结果中。我们可以使用stack来保存最终的结果，对于第i个字符，如果stack中top element 大于它，并且这个字符在i 之后还存在，那么我们可以将stack中的top element 删除，我们重复做这件事，直到stack 为空或者stack中的top element小于第i个字符，或者top element 在后续的字符串中不存在。为了检测stack 的top element 在后续字符串中是否存在，我们使用一个map 来存储字符出现的最后一个位置，只要这个位置大于i，则说明后续字符串还有这个元素。

实现

  public String removeDuplicateLetters(String s) {
       Stack<Character> stack = new Stack();
       Map<Character, Integer> last_occurance = new HashMap();
       char chs[] = s.toCharArray();
       for(int i = 0; i < chs.length; i++){
          last_occurance.put(chs[i], i);
       }
       Set<Character> seen = new HashSet();
       for(int i = 0; i < chs.length; i++){
          if(!seen.contains(chs[i])){
              while(!stack.isEmpty() 
                    && last_occurance.get(stack.peek()) > i
                    && chs[i] < stack.peek()){
                    seen.remove(stack.pop());
              }
              stack.push(chs[i]);
              seen.add(chs[i]);              
          }
       }
       StringBuilder sb = new StringBuilder();
        
        for(Character ch : stack){
            sb.append(ch);
        }
        return sb.toString();
    }