Leetcode — 3. Longest Substring Without Repeating Characters

The link to the problem: https://leetcode.com/problems/longest-substring-without-repeating-characters/

This problem requires us to find the length of the longest substring without repeating characters in the given string s.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols, and spaces.

For example, for input string = “abcabcbb”, the output should be 3 since the longest substring without duplicated chars is “abc”.

My thoughts:

My very first thought is to use 2 loops to compose a new substring that starts from the index i.
After composing a new substring, you need to again check if there are any duplicate characters in this substring.
The space complexity is O(1), but the time complexity is O(n³), which is pretty huge. (This code runs 438 ms on Leetcode two years ago. I know it because this was my lame solution at that time lol)

Then you can read the problem description more carefully. You can notice 2 things:

1. The output is the length. We don’t need to really form a substring since there’s no need to return the longest substring back.
2. s only consists of English letters, digits, symbols, and spaces. That is to say, there are limited numbers of characters.

Since we don’t need to record substrings, we can use a map to record the latest index of that character.

We can either use Map<Character, Integer> or an integer array to stores the latest index. It is not recommended to use Map<Character, Integer> in this case, since we know that there is a range of characters. Although it still works, it requires more complexity than using an array. (It requires 127ms on Leetcode also 2 years ago.)

Ok, so here comes my 2ms code, which beats 99% today (12/28/2020):

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n<=1)
            return n;
        int[] map = new int[128];
        Arrays.fill(map, -1);
        char[] c = s.toCharArray();
        int maxLen = 0;
        int startIndx = 0;
        for(int i=0;i<n;i++)
        {
            char cur = c[i];
            if(map[cur] >= startIndx)
                startIndx = map[cur]+1;
            maxLen = Math.max(maxLen, i-startIndx+1);
            map[cur] = i;
        }
        maxLen = Math.max(maxLen, n-startIndx);
        return maxLen;
    }
}

You might wonder how we know the size of our “map”. Java uses Unicode characters, which includes ASCII codes. The condition that characters here only contains those is all in the first 128 characters in ASCII. Click here to view all the characters in the ASCII table.

The idea:

We assume that we have an invisible substring, which starts from startIndx. That is to say, we only care if the current character appears in the range from startIndx to i. If the current character has appeared, we update startIndx by moving it to the next position of that duplicated character.

For example, we have an input string: “advdf”.
- i=0, startIndx = 0 (invisible substring is a)
- i=1, startIndx = 0 (invisible substring is ad)
- i=2, startIndx = 0 (invisible substring is adv)
- i=3, startIndx = 1 (invisible substring is vd) (since we give up the first d, and move startIndx to the next one)
- i=4, startIndx = 1 (invisible substring is vdf)

The time complexity of the code is O(n) since we only run one for loop and the space complexity is constant, O(1). ✌️