#340 - Longest Substring with At Most K Distinct Characters

Medium • View on LeetCode • View on GitHub

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

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var lengthOfLongestSubstringKDistinct = function(s, k) {
  const map = new Map();
  let result = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    map.set(s[right], (map.get(s[right]) || 0) + 1);

    while (map.size > k) {
      map.set(s[left], map.get(s[left]) - 1);
      if (map.get(s[left]) === 0) {
        map.delete(s[left]);
      }
      left++;
    }

    result = Math.max(result, right - left + 1);
  }

  return result;
};