K-Distinct Character Substring

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a string s consisting of lowercase English alphabets and an integer k. Your task is to find the length of the longest substring of s that contains exactly k distinct characters.

If no such substring exists, you should return -1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the string s.

The second line of input contains the integer k.

Output Format:

Print a single integer representing the length of the longest substring with exactly k distinct characters.

If no such substring is found, print -1.

Note:

A naive solution of checking every possible substring (O(N^2)) would be too slow for the given constraints.

Sample Input 1:

aabacbebebe
3

Sample Output 1:

Explanation for Sample 1:

We are looking for the longest substring with exactly 3 distinct characters.
- Substrings like `"aabac"` have 3 distinct characters (`a, b, c`) and length 5.
- The substring `"cbebebe"` has exactly 3 distinct characters (`c, b, e`) and has a length of 7. This is the optimal answer.

Sample Input 2:

aaaa
2

Sample Output 2:

-1

Explanation for Sample 2:

The string only contains one distinct character ('a'). It is impossible to form a substring with 2 distinct characters. Therefore, no valid substring exists.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= |s| <= 10^5
1 <= k <= 26

Time limit: 1 sec

Approaches (1)

Approach 1

Sliding Window

Time Complexity

Space Complexity

(100% EXP penalty)

K-Distinct Character Substring

Console