Example
Input
s = 'araaci', k = 2
Output
4
The longest substring with at most 2 distinct characters is 'araa' or 'araa' length 4.
Full lesson preview
Find the longest substring with at most K distinct characters
Given a string, find the length of the longest substring that contains at most K distinct characters using a sliding-window and frequency map.
Python practice15 minStrings – Sliding Window & FrequencyIntermediateLast updated March 25, 2026
Problem statement
You are given a string s and an integer k. Return the length of the longest substring of s that contains at most k distinct characters. Use a sliding-window approach and a frequency counter to maintain the number of distinct characters inside the current window efficiently. If k is 0, return 0.
Task
Implement an efficient sliding-window algorithm to compute the maximum length substring with at most K unique characters.
Examples
Input format
A function call longest_substring_k_distinct(s, k) where s is a string and k is a non-negative integer.
Output format
An integer representing the length of the longest substring with at most k distinct characters.
Constraints
0 <= len(s) <= 10^5; 0 <= k <= 10^5. Aim for O(n) time and O(min(n, alphabet)) extra space.
Samples
Sample 1
Input
s = 'cbbebi', k = 3
Output
5
The longest substring with at most 3 distinct characters is 'cbbeb' or 'bbebi' with length 5.