Finding the Longest Substring Challenge

Recently I was working on some Leetcode problems and I found some variations of the “longest substring”. Normally, you’ll be presented with a string and be asked to find the longest substring within the string that does not contain duplicates. More difficult variations of this problem result in more variations of the substring (specific characters, only 1 duplicate, etc.).

The trick to this challenge is just to use the “sliding window” concept where you essentially evaluate a window, and you move the space forward and backward based on what you find. There are many ways to do this as well, but if you use a HashMap I found it fairly simple to use the following solution (note that it is in Java):

Here you notice that as soon as a duplicate is found, the window moves to the location where the duplicate occurred. The HashMap is used to enable the algorithm to identify which characters occur where.

There is a really nice explanation (in depth) of this same type of solution here https://javaconceptoftheday.com/find-longest-substring-without-repeating-characters-java/

Hope the code I’ve presented here is fairly straightforward. Its another great example of the power of using a HashMap in your algorithms.

Originally published at https://rhythmandbinary.com on May 1, 2019.