Longest Substring with At Most K Distinct Characters

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

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"
public class Solution {
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return 0;
        int start = 0;
        int end = 0;
        int res = 0;
        Map<Character, Integer> charToCount = new HashMap<>();
        for (start = 0; start < s.length(); start++) {
            while(end < s.length()) {
                if (charToCount.containsKey(s.charAt(end))) {
                    int count = charToCount.get(s.charAt(end));
                    charToCount.put(s.charAt(end), charToCount.get(s.charAt(end))+ 1);
                } else {
                    if (charToCount.size() != k) {
                        charToCount.put(s.charAt(end), 1); 
                    } else {
                        break;
                    }
                }
                end++;
            }

            res = Math.max(res, end - start);
            if (end == s.length()) {
                break;
            }
            if (charToCount.containsKey(s.charAt(start))) {
                int count = charToCount.get(s.charAt(start)) - 1;
                if (count == 0) {
                    charToCount.remove(s.charAt(start));
                } else {
                    charToCount.put(s.charAt(start), count);
                }  
            }
        }
        return res;
    }
}

results matching ""

    No results matching ""