Longest Substring K Distinct

Medium

Python

def longest_substring_k_distinct(s,k):
    count={}; l=best=0
    for r,c in enumerate(s):
        count[c]=count.get(c,0)+1
        while len(count)>k:
            count[s[l]]-=1
            if count[s[l]]==0: del count[s[l]]
            l+=1
        best=max(best,r-l+1)
    return best

Java

public int lengthOfLongestSubstringKDistinct(String s,int k){
    Map<Character,Integer> count=new HashMap<>();
    int l=0,best=0;
    for(int r=0;r<s.length();r++){
        count.put(s.charAt(r),count.getOrDefault(s.charAt(r),0)+1);
        while(count.size()>k){
            count.put(s.charAt(l),count.get(s.charAt(l))-1);
            if(count.get(s.charAt(l))==0) count.remove(s.charAt(l));
            l++;
        } best=Math.max(best,r-l+1);
    } return best;
}

Key Insight

Python del vs Java remove(). Variable window logic identical.

Python → Java Differences

del vs map.remove()
dict.get() vs getOrDefault()
Variable window with freq map

Python

def longest_substring_k_distinct(s,k):
    count={}; l=best=0
    for r,c in enumerate(s):
        count[c]=count.get(c,0)+1
        while len(count)>k:
            count[s[l]]-=1
            if count[s[l]]==0: del count[s[l]]
            l+=1
        best=max(best,r-l+1)
    return best

Java

public int lengthOfLongestSubstringKDistinct(String s,int k){
    Map<Character,Integer> count=new HashMap<>();
    int l=0,best=0;
    for(int r=0;r<s.length();r++){
        count.put(s.charAt(r),count.getOrDefault(s.charAt(r),0)+1);
        while(count.size()>k){
            count.put(s.charAt(l),count.get(s.charAt(l))-1);
            if(count.get(s.charAt(l))==0) count.remove(s.charAt(l));
            l++;
        } best=Math.max(best,r-l+1);
    } return best;
}

Algorithm Steps

1. Track char freq
2. Shrink if >k distinct
3. Track max

← Previous All Sliding Window Next →