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));
Top comments (0)