Longest Substring with K-Repeating Characters

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a string s consisting of lowercase English letters and an integer k. Your task is to find the length of the longest substring of s in which the frequency of every character that appears in that substring is greater than or equal to k.

If no such substring exists, return 0.

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

Input Format:

The first line contains the string s.

The second line contains the integer k.

Output Format:

The function should return a single integer representing the length of the longest valid substring.

Note:

This problem can be elegantly solved using a divide-and-conquer strategy. The key insight is that if a character in a given string appears fewer than k times, it can never be part of a valid substring. Therefore, such a character acts as a "splitter." We can split the string by this character and recursively find the longest valid substring in the resulting parts.

Sample Input 1:

aaabb
3

Sample Output 1:

Explanation for Sample 1:

In the string "aaabb", 'a' appears 3 times and 'b' appears 2 times. Since k=3, 'b' is an invalid character. We can split the string by 'b', which gives us the substring "aaa". In "aaa", the frequency of 'a' is 3, which is >= k. The length is 3.

Sample Input 2:

ababbc
2

Sample Output 2:

Explanation for Sample 2:

In the string "ababbc", the character 'c' appears only once, which is less than k=2. Therefore, 'c' cannot be in the final substring. We split the string by 'c', which gives us the substring "ababb". We then check "ababb". Here, 'a' appears twice and 'b' appears three times. All character frequencies are >= k. The length is 5.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

1 <= s.length <= 10^4
s consists of only lowercase English letters.
1 <= k <= 10^5

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Longest Substring with K-Repeating Characters

Console