Longest Substring with K Unique Characters

给定一个字符串,找到最多有k个不同字符的最长子字符串。

样例

例如,给定 s = "eceba" , k = 3,
T 是 "eceb",长度为 4.

挑战

O(n), n 是所给字符串的长度

Solution

解法是维护一个sliding window,以及一个hash map, key是char,value是这个char在当前window中得出现次数。

start和end是当前字符串的起始和终止index。

当当前window 字符数超过k的时候,从start开始remove,只要遇到一个char的个数降为0的时候,可以跳出,因为说明当前window的char个数已经为k-1,满足条件。

如果字符集比较小的话可以维护一个int[]来对char计数。

Code

public class Solution {
    /**
     * @param s : A string
     * @return : The length of the longest substring
     *           that contains at most k distinct characters.
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        int start = 0;
        int res = 1;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put(s.charAt(0), 1);
        for (int end = 1; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch)+1);
            } else {
                if (map.size() == k) {
                    res = Math.max(res, end - start);
                    //full map, need to remove the first character in ths substring
                    for (int index = start; index < end; index++) {
                        map.put(s.charAt(index), map.get(s.charAt(index))-1);
                        start++;
                        if (map.get(s.charAt(index)) == 0) {
                            //have removed all occurance of a char
                            map.remove(s.charAt(index));
                            break;
                        }
                    }
                }
                map.put(ch, 1);
            }
        }
        res = Math.max(res, s.length() - start);
        return res;
    }
}