K-Repeating Substring

The first line of input contains the string str.

The second line of input contains the integer K.

Print a single integer representing the length of the longest valid substring.

A substring is a contiguous sequence of characters within a string.

The optimal solution uses a divide-and-conquer approach. If a character in the current substring appears less than K times, it cannot be part of the final longest substring. Therefore, the string can be split at this "invalid" character, and the problem can be solved recursively for the resulting substrings.

Sample Input 1:

aabbba
3

Sample Output 1:

6

Explanation for Sample 1:

The given string is "aabbba". The character 'a' appears 3 times and 'b' appears 3 times. Since every character appears at least K=3 times, the entire string is a valid substring. Its length is 6.

Sample Input 2:

ababacb
3

Sample Output 2:

0

Explanation for Sample 2:

In the string "ababacb", the character 'c' appears only once, which is less than K=3. Therefore, 'c' cannot be part of any valid substring. This invalidates the entire string. We can split the string by 'c' into "ababa" and "b".
- In "ababa", 'a' appears 3 times but 'b' appears only 2 times. This is also not a valid substring.
- In "b", 'b' appears only 1 time.
No valid substring can be formed, so the longest length is 0.

Expected Time Complexity:

The expected average time complexity is O(N).

Constraints:

1 <= K <= |str| <= 10^5
`str` consists of lowercase English letters only.

Time limit: 1 sec