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

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.

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.

--

--

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

Duncan McArdle

110 Followers

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