Longest Substring with At Most K Distinct Characters 386

Question

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

Example

For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge

O(n), n is the size of the string s.

Solution

用双指针解题。用一个hashmap记录遇到的字符及其出现次数。

1. 指针left和right都从0开始，right向后遍历数组。

2. 当right遇到字符是之前出现过的，则直接在hashmap中将其数量加1；若right遇到字符是之前没有出现过的，则分情况讨论1）若目前遇到过字符种类不足k个，则直接加入；2）若目前遇到过的字符种类大于k个，则移动左边界减少字符，直到字符种类少于k个后再加入。

3. 每次改变左边界时更新max的值。但是最后一次当right到数组尾部时，这一次不会改变左边界，所以要在循环结束后最后一次更新max。

代码如下：

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) {
        // write your code here
        if(s == null || s.length() == 0 || k == 0){
            return 0;
        }

        if(s.length() <= k){
            return s.length();
        }

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int left = 0;
        int right = 0;
        int max = 0;
        while(right < s.length()){
            //如果遇到的字符是之前出现过的，则直接将其数量加1
            if(map.containsKey(s.charAt(right))){
                map.put(s.charAt(right), map.get(s.charAt(right)) + 1);
            }else{
            //如果遇到的新字符之前没有出现过则分情况讨论
            //若目前遇到过字符种类不足k个，则直接加入
                if(map.size() < k){
                    map.put(s.charAt(right), 1);
                }else{
            //若目前遇到过的字符种类大于k个，则移动左边界减少字符，直到字符种类少于k个后再加入
                    max = Math.max(max, right - left);
                    while(map.size() >= k){
                        map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
                        if(map.get(s.charAt(left)) == 0){
                            map.remove(s.charAt(left));
                        }
                        left++;
                    }
                    map.put(s.charAt(right), 1);
                }
            }
            right++;
        }

        //right到底之后要统计最后一次substring的长度
        max = Math.max(max, right - left);

        return max;
    }
}