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);
        }
    }
}

All Problems

All Solutions