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

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

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Duncan McArdle

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.