Question

Formatted question description: https://leetcode.ca/all/316.html

 316	Remove Duplicate Letters

 Given a string which contains only lowercase letters,
 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.


 Example 1:

 Input: "bcabc"
 Output: "abc"


 Example 2:

 Input: "cbacdcbc"
 Output: "acdb"

 @tag-stack
 @tag-string

Algorithm

First use the hash table to record the number of occurrences of each letter, and then traverse the given string s to find the smallest letter. For each letter compared, the value in the hash table is reduced by 1. If it is 0 at this time, then Do-not continue traversing, at this time we recorded a position, delete all the characters on the left of that position in the string s, and delete all the reappearing letters on the right.

Just call this function recursively. Use replaceAll() function.

Code

Java

  • 
    public class Remove_Duplicate_Letters {
    
        public static void main(String[] args) {
            Remove_Duplicate_Letters out = new Remove_Duplicate_Letters();
            Solution s = out.new Solution();
    
            System.out.println(s.removeDuplicateLetters("cbacdcbc")); // acdb
        }
    
        // greedy. The runtime is O(26 * n) = O(n).
        public class Solution {
    
            // @todo: stack solution
    
            public String removeDuplicateLetters(String s) {
    
                /*
                System.out.println(s);
    
                    cbacdcbc
                    cdcbc
                    db
                    b
                */
                if (s.length() == 0) {
                    return "";
                }
    
                int[] cnt = new int[26];
                int pos = 0; // the position for the smallest s[i]
    
                // count char freq
                for (int i = 0; i < s.length(); i++) {
                    cnt[s.charAt(i) - 'a']++;
                }
    
    
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) < s.charAt(pos)) {
                        pos = i;
                    }
    
                    // find first char down to 0
                    // s[i] could be not s[pos], like `cdcbc`
                    // because need to lexicographical, any char before ==0 char need to be included
                    if (--cnt[s.charAt(i) - 'a'] == 0) {
                        break;
                    }
                }
    
                String rightSideString = s.substring(pos + 1);
                String next = rightSideString.replaceAll("" + s.charAt(pos), "");
                return s.charAt(pos) + removeDuplicateLetters(next);
            }
        }
    }
    
  • Todo
    
  • class Solution(object):
      def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        d = {}
        count = {}
        for c in s:
          d[c] = d.get(c, 0) + 1
          count[c] = count.get(c, 0) + 1
        stack = []
        cache = set()
        for c in s:
          if c not in cache:
            while stack and stack[-1] > c and d[stack[-1]] > 1 and d[stack[-1]] != 1 and count[stack[-1]] > 0:
              cache.discard(stack.pop())
            stack.append(c)
            cache.add(c)
          count[c] -= 1
        return "".join(stack)
    
    

All Problems

All Solutions