Google — Longest Substring with K Distinct Characters

Problem

Given string s and integer k, return the length of the longest substring with at most k distinct characters.

Example:

s = "eceba", k = 2 → 3  ("ece")
s = "aa", k = 1     → 2  ("aa")

Solutions

Python

from collections import defaultdict

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    if k == 0: return 0
    window = defaultdict(int)
    l = res = 0
    for r, c in enumerate(s):
        window[c] += 1
        while len(window) > k:
            window[s[l]] -= 1
            if window[s[l]] == 0:
                del window[s[l]]
            l += 1
        res = max(res, r - l + 1)
    return res

JavaScript

function lengthOfLongestSubstringKDistinct(s, k) {
    const w = new Map(); let l=0, res=0;
    for (let r=0; r<s.length; r++) {
        w.set(s[r],(w.get(s[r])||0)+1);
        while(w.size>k){const lc=s[l++];w.set(lc,w.get(lc)-1);if(!w.get(lc))w.delete(lc);}
        res=Math.max(res,r-l+1);
    }
    return res;
}

Java

import java.util.*;
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character,Integer> w=new HashMap<>(); int l=0,res=0;
    for (int r=0;r<s.length();r++) {
        w.merge(s.charAt(r),1,Integer::sum);
        while(w.size()>k){char lc=s.charAt(l++);w.merge(lc,-1,Integer::sum);if(w.get(lc)==0)w.remove(lc);}
        res=Math.max(res,r-l+1);
    }
    return res;
}

C++

#include <unordered_map>
#include <string>
using namespace std;
int lengthOfLongestSubstringKDistinct(string s, int k) {
    unordered_map<char,int> w; int l=0,res=0;
    for (int r=0;r<(int)s.size();r++) {
        w[s[r]]++;
        while((int)w.size()>k){if(--w[s[l]]==0)w.erase(s[l]);l++;}
        res=max(res,r-l+1);
    }
    return res;
}

C

int longestKDistinct(char* s, int k) {
    int freq[128]={}, distinct=0, l=0, res=0, n=strlen(s);
    for (int r=0;r<n;r++) {
        if(!freq[(int)s[r]]++) distinct++;
        while(distinct>k) if(!--freq[(int)s[l++]]) distinct--;
        if(r-l+1>res) res=r-l+1;
    }
    return res;
}