Skip to content

3. Longest Substring Without Repeating Characters

Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Intuition

Using hash set to track each character in the string. And set two pointers low and high to traverse the hold string.

  • When the hashset contains the same character with that at high pointer, keep moving low pointer right until the set has no duplicate characters
  • If current hashset do not has charachter at high pointer, add current character and move the high pointer right

During the traverse process, use max to store the maximum length of substring.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int low = 0;
        int high = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<>();

        while(high < s.length()) {
            if (set.contains(s.charAt(high))) {
                set.remove(s.charAt(low));
                low++;
            } else {
                set.add(s.charAt(high));
                high++;
            }
            max = Math.max(max, high - low);
        }
        return max;
    }
}

Approach (Optimal)

Note that s consists of English letters, digits, symbols and spaces, we initialize an array of size 128 to store the least position of each character in s. If this is duplication in a character c, we move the low pointer to "next position" store in the array to reduce the unnecessary comparsion.

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int[] arr = new int[128];
        int low = 0;
        int high = 0;
        while (high < s.length()) {
            low = Math.max(low, arr[s.charAt(high)]);
            max = Math.max(max, high - low + 1);
            // Store the 'next position' for low pointer to 'jump'
            arr[s.charAt(high)] = high + 1;
            high++;
        }
        return max;
    }
}