Question

Formatted question description: https://leetcode.ca/all/340.html

 340	Longest Substring with At Most K Distinct Characters

 Given a string, find the length of the longest substring T that contains at most k distinct characters.

 For example, Given s = “eceba” and k = 2,

 T is "ece" which its length is 3.

 @tag-string
 @tag-2pointers

Algorithm

Same as Longest Substring with At Most Two Distinct Characters.

  • change from 2 to k

Link at here.

Code

Java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Longest_Substring_with_At_Most_K_Distinct_Characters {
    public static void main(String[] args) {
        Longest_Substring_with_At_Most_K_Distinct_Characters out = new Longest_Substring_with_At_Most_K_Distinct_Characters();
        Solution_arrayAsMap s = out.new Solution_arrayAsMap();

        System.out.println(s.lengthOfLongestSubstringKDistinct("eceba", 2));
    }

    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if (s == null || s.length() == 0 || k <= 0) {
                return 0;
            }

            // char => its count in window
            Map<Character, Integer> map = new HashMap<>();
            int maxLen = 0;
            int left = 0;
            int right = 0;

            for (right = 0; right < s.length(); right++) {
                char c = s.charAt(right);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }

                // if distinct chars more than k
                if (map.size() > k) {
                    maxLen = Math.max(maxLen, right - left);

                    // Shrink the window size
                    while (map.size() > k) { // can be done by another counter variable
                        char leftChar = s.charAt(left);
                        int freq = map.get(leftChar);
                        if (freq == 1) {
                            map.remove(leftChar); // @note: remove by key
                        } else {
                            map.put(leftChar, freq - 1);
                        }
                        left++;
                    }
                }
            }

            // @note: final check
            if (left < s.length()) {
                maxLen = Math.max(maxLen, right - left);
            }

            return maxLen;
        }
    }

    public class Solution_arrayAsMap {

        public int lengthOfLongestSubstringKDistinct(String s, int k) {

            int[] countMap = new int[256];
            Set<Character> hs = new HashSet<>();

            int result = 0;
            int left = 0;
            int right = 0;

            while (right < s.length()) {

                char c = s.charAt(right);
                countMap[c]++;
                hs.add(c);

                if (hs.size() > k) {

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

                    while (hs.size() > k) {
                        if (--countMap[s.charAt(left)] == 0) {
                            hs.remove(s.charAt(left));
                        }
                        left++;
                    }
                }

                right++;
            }

            // @note: final check
            if (left < s.length()) {
                result = Math.max(result, right - left);
            }

            return result;
        }

    }
}

All Problems

All Solutions