Edward on Java with Leetcode: 3. Longest Substring Without Repeating Characters

Photo by Andrey Tikhonovskiy on Unsplash

Problem

Problem description is available at 3. Longest Substring Without Repeating Characters.

Algorithm

In a nutshell, I need to find out a maximum window that contains no repeating characters. This is a typical slide window problem. Assume a 2D window that can move along an 1D array, I can

1. fix the left side and keep moving the right side until there is a duplication.
2. I will move the left side till no repeat. Or even better if I can fast forward the left side without moving one place at a time.
3. Repeat #1 till the end of the array

Java Solution

In above #2, I mention the “fast forward the left side” which means if the right side now is charactor X, I want to see what’s the position of X in the existing window [left, right). The easiest way to achieve that is if I have a hashmap whose keys are charactors and values are positions.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0)
            return 0;
        int maxLen = 0;
        int left=0, right=0;
        Map<Character, Integer> map = new HashMap();
        while(right < len){
            //check if s[right] is in map and its position >= left
            char cur = s.charAt(right);
            int curExistingPos = map.getOrDefault(cur, -1);
            if (curExistingPos != -1 && curExistingPos>= left){
                //run into a repeating
                //calculate the window size and update the max value
                maxLen = Math.max(maxLen, right - left);
                //fast forward the left
                left = curExistingPos + 1;                
            }
            map.put(cur, right);
            right++;
        }
        return Math.max(maxLen, right - left);
    }
}

Java Knowledge

1. Java String has a length() method to get its length, which is different from length attribute of an array (see my previous post for more details).
2. String manipulation is very common and that’s why I want to read the official doc here . I cannot use s[index]but have to use s.charAt().
3. In my my previous post, I introduce some key functions of a Mapbut forget to mention getOrDefaultbut it does worth some attention.
4. Now comes with something new: Math.According to this article, Mathclass is included in java.langso I don’t need to explicitly import it. Here is the official doc which again worth a glimpse.