left=0, right=0). We expand window with right, and shrink it by moving left

Use a map to store frequency for each character in the current window.

Iterate over the string and insert new characters in the HashMap until we have exactly K distinct characters in the HashMap.

Iterate through the string, expanding the window by adding characters until we have exactly K distinct characters in the HashMap (representing the current longest substring with K unique characters).
If the window contains more than K distinct characters, shrink it from the left by removing the leftmost element from the HashMap, continuing until we have K or fewer distinct characters.

Code

[{"language":"Java","code":"class Solution {\n\n\tprivate int lengthOfLongestSubstringWithKUniqChars(String s, int k) {\n\t\tint n = s.length();\n\t\t// answer - length of longest substring with k uniq chars\n\t\tint ans = -1;\n\t\t// frequency map of chars in window\n\t\tMap<Character, Integer> windowCharCnt = new HashMap<>();\n\t\tint left = 0; // left = start of window, right end of window\n\t\tfor (int right = 0; right < n; right++) {\n\t\t\tchar c = s.charAt(right);\n\t\t\t\n\t\t\twindowCharCnt.put(c, windowCharCnt.getOrDefault(c, 0) + 1);\n\n\t\t\t// Shrink the sliding window\n\t\t\t// until we have exactly 'k' distinct characters in the window\n\t\t\twhile (windowCharCnt.size() > k) {\n\t\t\t\tchar leftChar = s.charAt(left);\n\n\t\t\t\twindowCharCnt.put(leftChar, windowCharCnt.get(leftChar) - 1);\n\n\t\t\t\tif (windowCharCnt.get(leftChar) == 0) {\n\t\t\t\t\twindowCharCnt.remove(leftChar);\n\t\t\t\t}\n\n\t\t\t\tleft++;\n\t\t\t}\n\n\t\t\tif (windowCharCnt.size() == k) {\n\t\t\t\tans = Math.max(ans, right - left + 1);\n\t\t\t}\n\t\t}\n\n\t\treturn ans;\n\t}\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tprivate</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> lengthOfLongestSubstringWithKUniqChars</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(String </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">s</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\tint</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> s.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">length</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">();</span></span>\n

Related Tags