316. Remove Duplicate Letters.md

316. Remove Duplicate Letters

---

leetcode Daily Challenge on October 11th, 2020.

leetcode-cn Daily Challenge on December 20th, 2020.

---

Difficulty : Medium

Related Topics : String、Stack、Greedy

---

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 100.00%, Memory Usage: 39.2 MB, less than 8.92% of Java online submissions

      // O(N)time
      // O(1)space
      public String removeDuplicateLetters(String s) {
          int[] record = new int[26];
          char[] arr = s.toCharArray();
          for (int i = 0; i < arr.length; i++) {
              record[arr[i] - 'a']++;
          }
          boolean[] added = new boolean[26];
          LinkedList<Integer> list = new LinkedList<>();
          for (int i = 0; i < arr.length; i++) {
              int j = arr[i] - 'a';
              if(added[j]) {
                  record[j]--;
                  continue;
              }
              while(!list.isEmpty() && j < list.getLast() && record[list.getLast()] != 0) {
                  added[list.removeLast()] = false;
              }
              list.add(j);
              added[j] = true;
              record[j]--;
          }
          StringBuilder sb = new StringBuilder();
          while (!list.isEmpty()) {
              sb.append((char) ('a' + list.removeFirst()));
          }
          return sb.toString();
      }
      

---

• the most votes

• Runtime: 3 ms, faster than 81.70%, Memory Usage: 38.9 MB, less than 8.92% of Java online submissions

  // O(N)time
  // O(1)space
  public String removeDuplicateLetters(String sr) {
      int[] res = new int[26]; //will contain number of occurences of character (i+'a')
      boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
      char[] ch = sr.toCharArray();
      for(char c: ch){  //count number of occurences of character
          res[c-'a']++;
      }
      Stack<Character> st = new Stack<>(); // answer stack
      int index;
      for(char s:ch){
          index= s-'a';
          res[index]--;   //decrement number of characters remaining in the string to be analysed
          if(visited[index]) //if character is already present in stack, dont bother
              continue;
          //if current character is smaller than last character in stack which occurs later in the string again
          //it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
          while(!st.isEmpty() && s<st.peek() && res[st.peek()-'a']!=0){
              visited[st.pop()-'a']=false;
          }
          st.push(s); //add current character and mark it as visited
          visited[index]=true;
      }
  
      StringBuilder sb = new StringBuilder();
      //pop character from stack and build answer string from back
      while(!st.isEmpty()){
          sb.insert(0,st.pop());
      }
      return sb.toString();
  }
  

---