Remove Duplicate Letters

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:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Analysis

Example "cbacdcbc"

1. pos->'a', i->'a', return "a" + removeDuplicateLetters("cdcbc")
2. pos->'c', i->'d', return "c" + removeDuplicateLetters("db")
3. pos->'d', i->'d', return "d" + removeDuplicateLetters("b")
4. pos->'b', i->'b', return "b" + removeDuplicateLetters("")
5. return ""

Sum up, return "acdb"

Code

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        int pos = 0; // the position for the smallest s[i]
        //统计string s里的字符数，放到cnt里
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            //只要后面的char比较小，pos就往后移，pos要指向最小的char
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            //一旦i指向的字母在从i开始的string里只出现一次，就要停下来
            if (--cnt[s.charAt(i) - 'a'] == 0) break; 
        }
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}

Reference

Leetcode