316. Remove Duplicate Letters

Question

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

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

Solutions

• Method 1: Greedy
  • what we are greedy for: we are greedy for a smaller lexicographical order.

      class Solution {
      public String removeDuplicateLetters(String s) {
          if(s.length() == 0) return "";
          char[] arr = s.toCharArray();
          int[] count = new int[26];
          for(char c : arr){
              count[c - 'a']++;
          }
          int pos = 0;
          // Greedy for the smallest lexicographical order until we meet a letter exist the last time.
          // We assume it is c.
          for(int i = 0; i < arr.length; i++){
              if(arr[i] < arr[pos]) pos = i;  // always greedy for the smallest lexicographical order for current letter.
              if(--count[arr[i] - 'a'] == 0) break;   // once we meet a letter exists the last time, we need to break.
          }
          // remove all c in current string and make it as the beginning of the result.
          String next = s.substring(pos + 1).replace(arr[pos] + "", "");
          return arr[pos] + removeDuplicateLetters(next);
      }
      }
    

• Method 2: Deque
  • The idea of deque is very same as previous one.

      class Solution {
      public String removeDuplicateLetters(String s) {
          int[] count = new int[26];
          char[] arr = s.toCharArray();
          for(char c: arr) count[c - 'a']++;
          boolean[] visited = new boolean[26];
          // Deque increasing.
          Deque<Character> dq = new LinkedList<>();
          for(char c : arr){
              count[c - 'a']--;   // remove the frequency of current letter.
              if(visited[c - 'a']) continue;  // means current character has already in the dq.
              // !dq.isEmpty(): Means current dq is not empty
              // dq.peekLast() > c: the end character in the dq has larger lexicographical order than c.
              // count[dq.peekLast() - 'a'] > 0: if end letter is at the last time appearence, it means we cannot remove it.
              while(!dq.isEmpty() && dq.peekLast() > c && count[dq.peekLast() - 'a'] > 0){
                  visited[dq.pollLast() - 'a'] = false;
              }
              visited[c - 'a'] = true;
              dq.offer(c);
          }
          StringBuilder sb = new StringBuilder();
          while(!dq.isEmpty()){
              sb.append(dq.poll());
          }
          return sb.toString();
      }
      }
    

Reference

1.Java solution using Stack with comments