[LintCode] 386 Longest Substring with At Most K Distinct Characters 解题报告

Description
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.


思路
这是一道“前向型”指针的题。我们维护两个指针i和j从头往下走。
同时，我们维护一个hash table。这里我用check数组和distinct分别表示hash table和hash table.size()。
我们知道如果从index a走到index b如果distinct char没有超过k，那么index a + 1加到index b肯定也不会超过k。这样我们就可以避免重复计算从index a + 1到index b这段。
如果我们沿着j走，并且把j这个位置上的字符放进hash table。当更新hash table的时候，我们看一下这时候的distinct char，如果已经是k了，还要加一个新的进去，那就超了，我们就要出内循环。出来以后要把i位置的char从表里把频率减1。如果减没了，还要更新distinct char的数量（减1）。




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) {
        // write your code here
        
        int max = 0;
        int i = 0;
        int j = 0;
        int distinct = 0;
        int[] check = new int[256];
        
        for (i = 0; i < s.length(); i++) {
            while (j < s.length()) {
                char c = s.charAt(j);
                if (check[c] > 0) {
                    check[c]++;
                }
                else {
                    if (distinct == k) {
                        break;
                    }
                    check[c]++;
                    distinct++;
                }
                j++;
            }
            
            max = Math.max(max, j - i);
            char c = s.charAt(i);
            check[c]--;
            if (check[c] == 0) {
                distinct--;
            }
        }
        
        return max;
    }
}