Longest Substring with At Most K Distinct Characters

medium sliding window hash map

Problem

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

Inputs = "eceba", k = 2

Output3

"ece" — 2 distinct, length 3.

def length_of_longest(s, k):
    cnt = {}
    l = best = 0
    for r, ch in enumerate(s):
        cnt[ch] = cnt.get(ch, 0) + 1
        while len(cnt) > k:
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0: del cnt[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

function lengthOfLongestSubstringKDistinct(s, k) {
  const cnt = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    cnt.set(s[r], (cnt.get(s[r]) || 0) + 1);
    while (cnt.size > k) {
      cnt.set(s[l], cnt.get(s[l]) - 1);
      if (cnt.get(s[l]) === 0) cnt.delete(s[l]);
      l++;
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map cnt = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt.merge(s.charAt(r), 1, Integer::sum);
            while (cnt.size() > k) {
                cnt.merge(s.charAt(l), -1, Integer::sum);
                if (cnt.get(s.charAt(l)) == 0) cnt.remove(s.charAt(l));
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

int lengthOfLongestSubstringKDistinct(string s, int k) {
    unordered_map cnt;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        cnt[s[r]]++;
        while ((int)cnt.size() > k) {
            if (--cnt[s[l]] == 0) cnt.erase(s[l]);
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

We want the longest stretch of the string that uses no more than k different characters. A sliding window with a small count map handles this neatly.

We keep a map cnt from character to how many times it appears in the current window. As the right pointer r moves, we bump the count for the new character. The number of distinct characters is simply the size of that map.

Whenever the map grows past k distinct keys, the window is illegal, so we walk the left pointer l forward, decrementing counts and deleting a key when its count hits zero, until we are back to k distinct. After each step we record the window length r - l + 1 in best.

Example: s = "eceba", k = 2. The window grows to "ece" with distinct {e, c}, length 3. Adding b would make 3 distinct, so we shrink. The best length found is 3.

Each character enters and leaves the window once, and the map never holds more than k+1 keys, so this is linear time with O(k) space.

Time: O(n) Space: O(k)