Finding the Longest Substring Challenge

(image source)

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):

  public int lengthOfLongestSubstring(String s) {

    char[] characterS = s.toCharArray();

    HashMap<Character, Integer> locations = new HashMap<Character, Integer>();

    int max = 0;

    for(int i = 0; i < characterS.length; i++) {
      if(locations.containsKey(characterS[i])) {
        i = locations.get(characterS[i]);
        i++;
        locations.clear();
      }

      locations.put(characterS[i], i);
      if(locations.size() > max) {
        max = locations.size();
      }
    }

    return max;
  }

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s