Longest substring with k distinct characters

Algorithm

• traverse the input string from first character to last character.
• at first the substring start at index 0.
• we increase the length of substring by one character.
• when the number of distinct characters in the substring is greater than input number.
• we find the new start index that make the number of distinct characters in the new substring is equal to input number and continue increase the length of new substring.

Code

public int lengthOfLongestSubstringKDistinct(String s, int size) {
        char[] sArray = s.toCharArray();
        Map<Character, Integer> map = new HashMap<Character, Integer>(); // key is character, value is its count
        int localLen = 0;
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char key = sArray[i];
            if (map.containsKey(sArray[i])) {
                int newCount = map.get(key) + 1;
                map.put(key, newCount);
            } else {
                map.put(key, 1);
                if (map.size() > size) {
                    localLen = i - start;
                    if (localLen > maxLen) {
                        maxLen = localLen;
                    }
                    while (map.size() > size) {
                        char preKey = sArray[start];
                        int count = map.get(preKey) - 1;
                        if (count == 0) {
                            map.remove(preKey);
                        } else {
                            map.put(preKey, count);
                        }
                        start++;
                    }
                }
            }
        }
        localLen = sArray.length - start;
        if (localLen > maxLen) {
            maxLen = localLen;
        }
        return maxLen;
    }

Complexity

• time complexity: O(N)
  • traverse each characters in the input string
  • each character is put in map once and removed from map once
• space complexity: O(K)