Longest Substring with K Distinct Characters

You are provided with a string S of length N, consisting of lowercase English alphabet letters, and a positive integer K.

Your task is to determine the maximum length of a substring of S that contains at most K distinct characters.

Example:

Input:

S = "bacda"
K = 3

Output:

4

Explanation:

The substrings that have at most 3 distinct characters include: "bac", "acd", "acda". The longest one is "acda" with a length of 4, hence the result is 4.

Constraints:

1

Question

Longest Substring with K Distinct Characters

You are provided with a string S of length N, consisting of lowercase English alphabet letters, and a positive integer K.

Your task is to determine the maximum length of a substring of S that contains at most K distinct characters.

Example:

Input:

S = "bacda"
K = 3

Output:

Explanation:

The substrings that have at most 3 distinct characters include: "bac", "acd", "acda". The longest one is "acda" with a length of 4, hence the result is 4.

Constraints:

1 <= T <= 10
1 <= K <= 26
1 <= N <= 10^4
All characters in the string are lowercase English alphabet letters.
Time Limit: 1 sec

Accepted Answer

Find the longest substring with at most K distinct characters in a given string.

Use a sliding window approach to keep track of the characters and their counts in the substring.
Maintain a hashmap to store the characters and their frequencies.
Update the window size and characters count as you iterate through the string.
Return the maximum length of the substring with at most K distinct characters.

Asked in Lifesight

Longest Substring with K Distinct Characters

Example:

Input:

Output:

Explanation:

Constraints:

Top Software Developer Interview Questions Asked at Lifesight

Interview Questions Asked to Software Developer at Other Companies

Top Skill-Based Questions for Lifesight Software Developer