Sliding Window - Longest Substring with At Least K Repeating Characters

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.

if no such substring exists, return 0.

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

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.

Constraints:

1 <= s.length <= 10⁴
s consists of only lowercase English letters.
1 <= k <= 10⁵

Solution 1 - Using sliding window technique, keep track of longest substring with at least 'k' repeating characters substring

In this approach, we will first capture the characters frequency in input string s into an array of size 26 (each represents lowercase alphabet count). Then, we will find find where the breaks are in input string, i.e. if any charater appeared less than k times, this character cannot be part of substring and it breaks the string into to two substrings, then we repeat this process on two substrings in a recursive fashion and keep track of maximum length substring which has characters appeared atleast k times.

Let's understand with an example, say the input string is s = "ababbbcadd" and k=3

Problem 1a illustration

First, let's get the character's frequency of input string s into a Map, this is how it looks like.
From the above frequency count, we know for sure, longest substring cannot contain 'c' or 'd', since their count is less than k. This also means that these characters will split the input string into two parts, so the longest substring could be either left or right sides.
Next, we iterate over each character, and when we reach letter 'c', we know that this letter cannot be part longest substring, since it did not appeared at least k times. Now this occurrence will break the input string into two parts, substring on the left side of letter 'c' and the substring on the right side.
Now we have to repeat the above steps on smaller input strings s1 = "ababbb" and s2 = "add".
Let's construct characters frequency of s1 and s2.
Let's continue with the substring s1 and understand the intution behind the solution, from the characters frequency map of s1, we know that character 'a' appeared only 2 times, which is less than k. So, this cannot be part of longest substring, and it will split the string into parts. There are no characters on the left side of first occurrence of character 'a' so we can ignore the left side substring, and the substring on right side will be s3="babbb".
Next, construct the characters frequency map of s3 = "babbb".
From the frequency map of s3, we know letter 'a' cannot be part of longest substring, since it appeared only one time, so letter 'a' is going to split the string s3 into two parts. Substring on left side has lesser characters than k, so we can ignore that, and the substring on right side will be s4="bbb"
Next, construct the characters frequency map of s4 = "bbb".
This is a valid substring and has each character appeared atleast k times, so the answer is 3.
So, what we essentially did is, we split the input string into smaller substrings based on the occurrence of letters that appeared less than k times, and recusrively applied the solution on smaller input strings.
Time complexity of this solution is going to be O(n), where n is the length of input string s, this is because we are iterating the through input string once and for each substring we capturing character frequency map, since there are 26 characters in lowercase alphabets, that will be O(26) * O(n) => O(n).

Implementation steps:

First, we will create a helper function that takes input string s, left starting position of current substring, right ending position of current substring, and k.
Next, check if the current substring's length is less than k, i.e. right -left < k, this means there are not enough characters in this substring, so we return result as 0.
Next, create an integer array of size 26 and capture characters frequency of input string, since the input can only contain lowercase alphabets, so there can only be 26, call it charsFrequency.
Next, create following 3 variables:
- result: we will use this to store the result, we will initialize this with 0.
- start: we will use this to store the starting index for next substring, we will initialize with left pointer to start with.
- isValid: we will use this to check if all the characters in current substring are valid or not, we will initialize this with true.
Next, iterate from i = left pointer to right pointer, and do the following:
- Check if the current character at i pointer is appeared lesser than k times, if it is, then recursively call the helper function from from left pointer until where this condition occurred. We are essentially checking if the left substring has the valid longest substring or not. Also, update isValid to false and update the start pointer to i+1 inorder to skip this letter for the right side substring.
Next, check if isValid is still true, this means that the entire string is valid and is the longest substring, otherwise recursively call helper function from start position to the end of string right.

public class LongestSubstringWithAtleastKRepeatingChars { static int longestWithAtleasetKRepeating(String s, int k) { return helper(s, 0, s.length(), k); } static int helper(String s, int left, int right, int k) { if(right - left <k) { return 0; } int[] charsFrequency = new int[26]; for(int i=left; i<right; i++) { charsFrequency[s.charAt(i)-'a']++; } boolean isValid = true; int start =0; int result =0; for( int i=left; i<right; i++) { if(charsFrequency[s.charAt(i)-'a'] <k) { result = Math.max(result, helper(s, left, i, k)); isValid = false; start = i+1; // move to next position } } return isValid ? right - left : Math.max(result, helper(s, start, right, k)); } public static void main(String[] args) { System.out.println(longestWithAtleasetKRepeating("aaabb", 3)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input string s.
Space complexity: O(n), space that will be used by recursive calls stack, since there can be n substrings.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: