Remove Duplicate Letters

Problem

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"

Solution

Recursive Greedy Solution: O(n) time

public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() < 2) return s;
        int[] counts = new int[26];
        for (char ch : s.toCharArray()) counts[ch - 'a']++;
        int minPos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(minPos)) minPos = i;
            if (--counts[s.charAt(i) - 'a'] == 0) break; 
        } 
        return s.charAt(minPos) + removeDuplicateLetters(s.substring(minPos + 1).replaceAll(s.charAt(minPos) + "", ""));
    }
}

Analysis

The idea of this solution is to find the unique letter and apply recursion with smallest letter at the beginning
We use int[26] to store the frequency of each letters and decrement the frequency as we see them
Also we record the smallest letter in lexicographical order
We break the loop immediately when we face a unique letter
Then we recursively call the method with the character at minPos and substring after it with its duplicates removed

Notice that the time complexity is O(n) because the each recursive method takes O(n) time
And the recursive method will be called at most 26 times because of the replaceAll() method
Every time there is one kind of letter is removed completely from the string and there are at most 26 different lower case letters