Description

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

1Input: s = "eceba", k = 2
2Output: 3
3Explanation: The substring is "ece" with length 3.

Example 2:

1Input: s = "aa", k = 1
2Output: 2
3Explanation: The substring is "aa" with length 2.

Constraints:

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 50

Solution

This solution uses sliding window technique with hashing data structure. The idea is that we need to find distinct string count. For this we use HashMap to store the unique keys. When the key count increases above k, we know our window is invalid. At this point, we have to make the window valid again, so we remove keys one by one. Every time, we check if the current window is larger than previously seen window. If it is, then that will be the longest substring.

 1class Solution {
 2    public int lengthOfLongestSubstringKDistinct(String s, int k) {
 3        int left = 0, right = 0, max = 0;
 4        Map<Character, Integer> map = new HashMap<>();
 5        while (right < s.length()) {
 6            char c = s.charAt(right);
 7            map.put(c, map.getOrDefault(c, 0) + 1);
 8            // When window becomes invalid, start contracting
 9            while (map.size() > k) {
10                char leftChar = s.charAt(left);
11                map.put(leftChar, map.get(leftChar) - 1);
12                if (map.get(leftChar) == 0) {
13                    map.remove(leftChar);
14                }
15                left++;
16            }
17            max = Math.max(max, right - left + 1);
18            right++;
19        }
20        return max;
21    }
22}
  • Time Complexity: O(n)
  • Space Complexity: O(k)