Leetcode: 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"

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

1. find out the last appeared position for each letter; c - 7 b - 6 a - 2 d - 4
2. find out the smallest index from the map in step 1 (a - 2);
3. the first letter in the final result must be the smallest letter from index 0 to index 2;
4. repeat step 2 to 3 to find out remaining letters.

• the smallest letter from index 0 to index 2: a
• the smallest letter from index 3 to index 4: c
• the smallest letter from index 4 to index 4: d
• the smallest letter from index 5 to index 6: b

so the result is "acdb"

Notes:

• after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
• in step 3, the beginning index of the search range should be the index of previous determined letter plus one

Code (Java):

public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        
        // Step 1: find the last index for each char
        Map<Character, Integer> lastIndexMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            lastIndexMap.put(c, i);
        }
        
        // Step 2: for each character, find the smallest index in the map
        // Then find out the smallest char before the index.
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = findSmallestIndex(lastIndexMap);
        
        while (!lastIndexMap.isEmpty()) {
            char curr = 'z' + 1;
            int index = 0;
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if ((c < curr) && (lastIndexMap.containsKey(c))) {
                    curr = c;
                    index = i;
                }
            }
            
            // append result
            sb.append(curr);
            lastIndexMap.remove(curr);
            
            // update the start and end
            start = index + 1;
            end = findSmallestIndex(lastIndexMap);
        }
        
        return sb.toString();
    }
    
    private int findSmallestIndex(Map<Character, Integer> lastIndexMap) {
        int result = Integer.MAX_VALUE;
        for (int index : lastIndexMap.values()) {
            result = Math.min(result, index);
        }
        
        return result;
    }
}