Today I want to talk about the longest substring with repeating characters algorithm available to try at leetcode.com, and how this algo kicked my butt. I’ve been working on algorithms quite a bit lately, and have even come to enjoy them. I’m still not very good at them, but starting to feel more and more confident each day. So walking into this particular problem, I was feeling myself. Unfortunately, it took me by surprise and quite a bit of time to figure out. Let’s take a look!
The Problem
As pictured above, the prompt asks for a function that takes in a string, and to return the length of the longest substring that doesn’t have any repeating characters. Simple enough. In the above example, “abcabcbb” would yield “abc” or 3. Whereas “pwwkew” would also yield 3, since the longest substring would be “wke”. Note that “pwke” would not be correct, it would need to be a proper substring.
The Solution
I knew this would need to be a two-pointer solution, one pointing at the starting point, and another determining how far we could go before reaching a duplicate character. Therefore, I landed on using nested loops. However, figuring out behavior for the loops proved to be tricky. We would need a counter to determine the longest substring as we looped through, but I was having a hard time determining where we would reset the loop after reaching a duplicate. Eventually, I figured out that I actually needed the external loop to be the loop that was checking the length of the substring. I originally thought that our first pointer, i, from our external loop would be our starting point and j, our internal loop pointer, would find our end point. However, these needed to be flipped and our internal loop needed to check our starting position and compare it externally, with the help of a separate variable. Here’s where we ended.
So, what is happening here is we have our first loop, and then our second loop that only runs if j is less than i with j initializing to the value of k. It then checks s[i] against s[j] and if they are equal, we break our loop after increasing the value of k. We are never running our internal loop until i is ahead of j in the string, and when we find a repeat character, we reset the check to start past that repeated character. Before we have completely run through our string, we check our max value against the value of i— k + 1 and return the largest number. We have +1 there to account for the minimum substring, since we only return 0 if the string is empty and are comparing zero-based indexes. Afterward, we return max. A though one to wrap my head around initially, but we got there eventually.
I hope this helps! Keep practicing algos!
