Longest Substring Contains m Unique Characters

题目地址：
http://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/

题目：

Given a string you need to print longest possible substring that has exactly M unique characters. If there are more than one substring of longest possible length, then print any one of them.

Examples:

"aabbcc", k = 1
Max substring can be any one from {"aa" , "bb" , "cc"}.

"aabbcc", k = 2
Max substring can be any one from {"aabb" , "bbcc"}.

"aabbcc", k = 3
There are substrings with exactly 3 unique characters
{"aabbcc" , "abbcc" , "aabbc" , "abbc" }
Max is "aabbcc" with length 6.

"aaabbb", k = 3
There are only two unique characters, thus show error message. 

解题思路：
这道题是用map来存储，然后key是char，value是该char最后出现的位置。

代码：

public class LongestSubstringContainsmUniqueCharacters {

    public String findSub(String s, int m){
        if(s == null || s.length() == 0){
            return s;
        }
        String rst = "";
        // the value will store the last occurrence of the character        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        for(int i = 0; i <= s.length() - 1; i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c, i);
            }
            else{
                map.put(c, i);
                if(map.size() == m + 1){
                    // find the last occurrence of all char in the map and store the smallest one in lastIndex                    int lastIndex = s.length();
                    for(char ch : map.keySet()){
                        lastIndex = Math.min(lastIndex, map.get(ch));
                    }
                    // find the char with lastIndex and                    map.remove(s.charAt(lastIndex));
                    left = lastIndex + 1;
                }
            }
            if(map.size() == m){
                String temp = s.substring(left, i + 1);
                rst = temp.length() > rst.length() ? temp : rst;
            }
        }
        return rst;
    }

    public static void main(String[] args){
        //4 (aaba) for m = 2 unique characters        //7 (beabbee) for m = 3 unique characters        LongestSubstringContainsmUniqueCharacters longestSubstringContainsmUniqueCharacters = new LongestSubstringContainsmUniqueCharacters();
        String s1 = "aabacdadd";
        String s2 = "beabbee";
        String s3 = "aaaaaaaaaaaaaabbbbbccd";
        String rst1 = longestSubstringContainsmUniqueCharacters.findSub(s1, 2);   // should be "aaba" or "dadd"        String rst2 = longestSubstringContainsmUniqueCharacters.findSub(s2, 3);   // should be "beabbee"        String rst3 = longestSubstringContainsmUniqueCharacters.findSub(s3, 2);   // should be "aaaaaaaaaaaaaabbbbb"        System.out.println(rst1);
        System.out.println(rst2);
        System.out.println(rst3);
    }

}