Longest Substring with At Most K Distinct Characters

Description

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

Hint

Train of Thought

建一个hashmap存字母和出现次数, 双指针挪动, 如果map的size大于k了, 左指针开始动, 直到map里面能remove掉一个key-value pair为止

Code

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() <= k) {
            return s.length();
        }

        //use int[256] instead of hashmap

        int[] map = new int[256];
        int left = 0, numOfChar = 0, max = 0;

        for (int i = 0; i < s.length(); i++) {
            if (map[s.charAt(i)] == 0) {
                map[s.charAt(i)]++;
                numOfChar++; 
            } else {
                map[s.charAt(i)]++;
            }

            if (numOfChar > k) {
                while (map[s.charAt(left)] > 1) {
                    map[s.charAt(left)]--;
                    left++;
                }
                map[s.charAt(left)]--;
                numOfChar--;
                left++;
            }
             max = Math.max(max, i - left + 1);
        }

        return max;


    }
}

Complexity