Longest Substring With At Least K Repeating Characters - Leetcode Solution

Problem Statement:

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2 Output: 5 Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Approach:

The problem is to find the longest substring with at least k repeating characters in a given string. We can use the brute-force approach to solve this problem by considering all possible substrings of the string and count the frequency of each character in the substring. However, this approach is not efficient, and it will take a lot of time to find the result for a large-sized string.

An efficient approach to solve this problem is to use a divide and conquer approach, which involves specifically splitting the input string into substrings. First, we need to count the frequency of all characters in the given string. Then we will divide the string into substrings whenever we encounter a character whose frequency is less than k. We will then recursively apply the same procedure to these substrings. Finally, we will return the length of the longest substring that fulfills the condition that the frequency of each character is greater than or equal to k.

Algorithm:

1. initialize an array 'freq' of size 26, and initialize all its elements to zero.
2. count the frequency of each character in the given string and store it in the 'freq' array.
3. for each character of the given string a. if the frequency of the character is less than k i. divide the string into substrings at the current index - all the substrings obtained in this way will contain fewer than k occurrences of the current character ii. recursively apply the same procedure to these substrings
4. if all characters in the substring have frequency greater than or equal to k, return the length of the substring. else return 0.

Time Complexity:

The Time complexity for this algorithm is O(n log n), where 'n' is the length of the string. The time complexity of the divide and conquer algorithm is O(n log n) because the string is divided into smaller substrings and the process is repeated recursively.

Space Complexity:

The space complexity for this algorithm is O(1). We are using a fixed amount of space to store the frequency of each character. However, if we use a hash map to count the frequency, the space complexity will increase to O(n).

Code:

class Solution { public: int longestSubstring(string s, int k) { int n = s.size(); if(n == 0 || n < k) return 0; if(k == 1) return n; int freq[26] = {0}; for(int i = 0; i < n; i++) freq[s[i]-'a']++; int i = 0; while(i < n && freq[s[i]-'a'] >= k) i++; if(i == n) return n; int left = longestSubstring(s.substr(0, i), k); while(i < n && freq[s[i]-'a'] < k) i++; int right = longestSubstring(s.substr(i), k); return max(left, right); } };

Explanation:

In this implementation, we have used the divide and conquer approach to solve the problem. We have taken a string 's' and an integer 'k' as input. We first check if the size of the string is 0 or less than k. If it is, then we return 0 as there is no substring of length k in the given string. If k is 1, then the entire string is the substring with at least k repeating characters, so we return the size of the string.

We initialize an array 'freq' of size 26, and initialize all its elements to zero. We then count the frequency of each character in the given string and store it in the 'freq' array.

We then traverse the string and check if the frequency of the current character is less than k. If it is, we split the string at the current index by calling the 'substr' function and recursively apply the same procedure to the resulting substrings.

If all characters in the substring have frequency greater than or equal to k, we return the length of the substring. Otherwise, we return 0.

In this code, we have used a recursive function 'longestSubstring' to implement the divide and conquer approach. The function takes a string 's' and an integer 'k' as input and returns the length of the longest substring having at least k repeating characters.

In the function, we first check if the size of the string is 0 or less than k. If it is, then we return 0 as there is no substring of length k in the given string. If k is 1, then the entire string is the substring with at least k repeating characters, so we return the size of the string.

We then check if all characters in the given string have frequency greater than or equal to k. If it is, we return the size of the string.

If all characters in the string do not have frequency greater than or equal to k, we find the first character whose frequency is less than k and split the string at that point using the 'substr' function. We then recursively apply the same procedure to the resulting substrings.

Finally, we return the maximum length of the substrings returned by the recursive calls.

Conclusion:

In this problem, we have calculated the length of the longest substring having at least k repeating characters in a given string using a divide and conquer approach. We have used the frequency of characters to divide the string into smaller substrings and recursively applied the same procedure to these substrings. The time complexity of this algorithm is O(n log n), and the space complexity is O(1).

1