Coding

Longest Substring With At Most K Distinct Characters

Asked at

BitGo

Groww

Paytm

Salesforce

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s and an integer k.Find the length of the longest substring with at most k distinct characters.

Input : s = "aababbcaacc" , k = 2 Output : 6 Explanation : The longest substring with at most two distinct characters is "aababb". The length of the string 6.

Input : s = "abcddefg" , k = 3 Output : 4 Explanation : The longest substring with at most three distinct characters is "bcdd". The length of the string 4.

Input : s = "abccab" , k = 4

1 <= s.length <= 105
1 <= k <= 26

cpp

class Solution {
public:
    int kDistinctChar(string& s, int k) {
        //your code goes here
    }
};

java

class Solution {
    public int kDistinctChar(String s, int k) {
        //your code goes here
    }
}

python

class Solution:
    def kDistinctChar(self, s, k):
        #your code goes here

javascript

class Solution {
    kDistinctChar(s, k) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int kDistinctChar(string s, int k)
    {
        //your code goes here
    }
}

func kDistinctChar(s string, k int) int {
	
}

Stuck? Show a way to structure it+

01Expand the right boundary and increment that character's frequency.
02While the number of distinct characters exceeds k, shrink from the left.
03Record the largest valid window after restoring the invariant.
04Handle k equal to zero without admitting a non-empty window.

Reference answer

Use a frequency map for the current window and two pointers. For each right index, increment the new character's count. While the map contains more than k distinct characters, decrement the character at the left boundary, erase it when its count becomes zero, and advance left. Once the window is valid, update the answer with right - left + 1. The window after shrinking is the longest valid window ending at this right index because left moved only as far as necessary. Both pointers advance monotonically, so time is O(n) and the map uses O(k) space for a valid window, or O(alphabet size) in general. If k is zero, no non-empty substring is valid and the answer is zero. Do not clear the entire map when a violation occurs; shrinking preserves reusable characters and is what makes the scan linear.

Then expect these follow-ups

How would you count substrings with exactly k distinct characters?
Tests: window transformation
Why does each pointer move at most n times?
Tests: complexity

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question