K Characters Substring

In this approach, we can traverse over every substring of the given string and check if all of its characters have a minimum frequency of ‘K’.

If a substring has all characters with a minimum frequency of ‘K’ we try to update our solution with its length.

We will create an isStringValid(subStr, k) method, that checks if the ‘subStr’ has all characters with a minimum frequency of k.

Algorithm:

• In the isStringValid(subStr, k) method
  • Create array freq, and store the frequency of each character in the string ‘subStr’ in freq map.
  • Iterate key over freq
    • If freq[key] is less than K return False
  • At the end of the function return True.
• In the given function
  • Set ans as 0
  • Iterate i from 0 to the length of the string
    • Iterate j from i + 1 to the length of the string
      • If isStringValid(substring of string from i to j, k) is True
        • Set ans as the maximum of itself and length of the substring of string from i to j.
  • Return ans

In this approach, we will use the sliding window approach to find the window of the biggest length.

For Example, if we have string = ‘aabbb…’ and K = 3, what should we do when we reach the window ’aabbb’.

One way to handle this problem is to do several sliding window passes, where we fix diffChars, the number of different symbols we must have in our substring. So, we check all possible diffChars = 1, ... 26 (if fact, not 26, but the number of unique characters in the string) and do a sliding window pass.

Algorithm:

• Set ans as 0
• Initialise a set uniqueChars and insert every character of the string in it.
• Iterate allowedUniqueChars from 0 to length of uniqueChars
  • Set left, right, found and charsSubStr as 0
  • Set freqCount as an array of size 26 initialised with 0.
  • While right is less than the length of the string
    • If charsSubStr is not greater than allowedUniqueChars
      • Set newSym as ASCII value of string[right] - 97
      • Increase freqCount[newSym] by 1
      • If freqCount[newSym] is 1, increase charsSubStr by 1
      • If freqCount[newSym] is K, increase found by 1
      • Increase right by 1
    • Otherwise,
      • Set symb as ASCII value of string[left] - 97
      • Increase left by 1
      • If freqCount[symb] is K, decrease found by 1
      • Decrease freqCount[symb] by 1
      • If freqCount[symb] is 0, decrease charsSubStr by 1
    • If charsSubStr and found are both equal to allowedUniqueChars
      • Set ans as the maximum of itself and right - left 
• Return ans

In this approach, we will count the frequencies of all characters in the string. We know that any character which has a frequency less than K, won't be part of a valid substring so if we find a character with less than K frequency, we can divide the string on either side of that character and recursively call our function.

Algorithm:

• If the length of the string is 0 or less than K, return 0
• If K is less than 2 return the length of string
• Initialise an array freqCount and store the frequency of each character in the string in freqCount hashmap.
• Set index as 0.
• While the index is less than the length of string and freqCount[string[index]] is greater than K, increment index by 1.
• If index is equal to the length of the string return index
• Set leftAns as maxSubStringKchars(substring of string from 0 to index, k)
• While the index is less than the length of string andreqCount[string[index]] is less than K, increment index by 1.
• If the index is less than the length of the string set rightAns as maxSubStringKchars(substring of string from index, k), otherwise set it as 0
• Return the maximum of leftAns and rightAns.