DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on • Updated on

Longest Substring With K Distinct Characters

Problem Statement #
Given a string, find the length of the longest substring in it with no more than K distinct characters.

Example 1:

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

const longestSubstringWithKDistinctCharacters = (str, k) => {
  let map = new Map();
  let temp = "";
  let max = 0;
  let stri = "";
  let end = 0;

  while (str.length > end) {
    const nextChar = str[end];

    if (map.size < k && !map.has(nextChar)) {
      map.set(nextChar, 1);
      temp = temp + nextChar;
      end++;
    } else if (map.size <= k && map.has(nextChar)) {
      map.set(nextChar, map.get(nextChar) + 1);
      temp = temp + nextChar;
      end++;
    } else if (map.size === k && !map.has(nextChar)) {
      while (map.size === k) {
        // save the current
        if (temp.length > max) {
          max = temp.length;
          stri = temp;
        }

        let startValue = temp[0];
        map.set(startValue, map.get(startValue) - 1);
        if (map.get(startValue) === 0) {
          map.delete(startValue);
        }
        temp = temp.substring(1);
      }
    }
  }
  return stri;
};

console.log(longestSubstringWithKDistinctCharacters("csbebbbi", 3));
console.log(longestSubstringWithKDistinctCharacters("araaci", 2));
console.log(longestSubstringWithKDistinctCharacters("araaci", 1));
console.log(longestSubstringWithKDistinctCharacters("cbbebi", 3));


Enter fullscreen mode Exit fullscreen mode

Top comments (0)