LeetCode problem #395: Longest substring with at least K repeating characters(JavaScript)

In this LeetCode problem, we’re given a string str and an integer k, and asked to return the longest substring of str, which is made up only of characters that appear k or more times.

In other words, given the string ‘aabbbcccc’ and a k value of 3, the longest substring where all letters appear 3 or more times would be ‘bbbcccc’, so our answer would be 7.

Solution #1: Brute force

The most obvious brute force solution is to construct every possible substring, and then check if it is made up entirely of characters that appear k or more times. To do this, we loop through every character in the provided string, and then again loop from that point onwards. At each stop, we check if the current substring consists entirely of characters that appear k or more times, and then store them as the longest substring found, if in fact they are.

There are a number of performance improvements that can be made to this code, but at the end of the day it can’t compete with the more efficient solutions out there.

Solution #2: Divide and conquer

For this approach, we first create a map of all letters in str, recording the number of times that each letter occurs. Next, we loop through str until we reach a letter which appears less than k times. As we know this letter cannot be a part of the answer, we can “break” at this point, and look at the string starting at the previous break, and ending at this one.

Note: If there is no “break” in the string, then the entire string is valid.

The clever part here is that we can call the same function again, this time passing in the new string, to check if it itself is valid. This creates a recursive call that divides the string down and down until it reaches a point where it is the longest potential substring.

For example, given the string ‘aaabcccc’ and a k of 3, we can see that the string will break when it reaches ‘b’. This will then call the function again on ‘aaa’, which is valid, and so 3 will be returned as the longest substring’s length. The original loop will then continue until it reaches the end of the string, at which point it will check ‘bbbb’, which is also valid, and will return 4. This is of course the higher of the 2 numbers, and so 4 becomes our answer.