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

Hiring now

Salesforce has 1,420 open roles right now

Also hiring: Paytm, BitGo, Groww

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Business Development Representative Belgium Market (Dutch Speaking)
Ireland - Dublin
Service Cloud Account Executive
France - Paris
Summer Intern 2027 - Content Writer
India - Bangalore

Or practice this question first

Next question