Problem

Given a string, find the length of the longest substring without repeating characters.

Examples

Example 1:

1
2
3

Input: s = "aababcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc".

Example 2:

1
2
3

Input: s = "cccc"
Output: 1
Explanation: The longest substring without repeating characters is "c".

Example 3:

1
2

Input: s = ""
Output: 0

Solution

Method 1 - Brute Force

The trivial solution would be to do double for loop and from each position try to find the longest substring until we see a duplicate char. This is O(n^2) solution.

Another approach is we can generate substrings and check if all chars are unique, like “Determine if a string has all unique characters” in CC 150..

Method 2 - Sliding Window with Set🏆

This problem is similar to the previous problem - Longest Substring with K distinct characters

Finding the Longest substring without repeating characters is same as finding the Longest substring with All distinct characters. So instead of K distinct characters we have to find the longest substring where all characters are distinct.

We start with a window and maintain a hashset for that window. We keep on adding chars to window and slide window to right, till they are not duplicate. If we find duplicate we keep moving the left pointer to shrink window, till we remove that duplicate char from the set. In meantime, we will keep check of the longest window.

Let windowStart is left and windowEnd is right.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int lengthOfLongestSubstring(String s) {
	// Note: The Solution object is instantiated only once and is reused by each test case.
	int maxLength = 0;

	// left is first pointer, right is second pointer
	HashSet<Character> set = new HashSet<Character>();
	int left = 0;
	int right = 0;
	while (right < s.length()) {
		char c = s.charAt(right);
		if (set.contains(c)) {
			set.remove(s.charAt(left));
			left++;
		} else {
			set.add(c);
			right++;
			maxLength = Math.max(maxLength, set.size());
		}
	}

	return maxLength;
}

Method 3 - Sliding Window with Frequency Map🏆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public int lengthOfLongestSubstring(String s) {
	int n = s.length();

	// answer - length of longest substring with no repeating chars
	int ans = -1;
	// frequency map of chars in window
	Map<Character, Integer> windowCharCnt = new HashMap<>(); 
	int left = 0;

	for(int right = 0; right < n; right++) {
		char c = s.charAt(right);
		windowCharCnt.put(c, windowCharCnt.getOrDefault(c, 0) + 1);

		while(windowCharCnt.size() < right - left + 1) {
			char leftChar = s.charAt(left);

			windowCharCnt.put(leftChar, windowCharCnt.get(leftChar) - 1);
			if(windowCharCnt.get(leftChar) == 0) {
				windowCharCnt.remove(leftChar);
			}

			left++;  
		}

		if(windowCharCnt.size() == right-left+1) {
			ans = Math.max(ans, right-left+1);
		}
	}

	return maxLen;  
}

Method 3 - Sliding Window with Boolean array as set 🏆

We can use a flag array to track the existing characters for the longest substring without repeating characters.

When we realize that substring “abcc” has dups, we can immediately abandon the whole substring and check substrings from “cdefgh”. Thus, we have the following approach:

  1. Keep two pointers (start, end) that denotes the current substring we’re checking and both has an initial value of 0.
  2. Each time, move forward end pointer by 1 character and use the hashset to check if the newly added character has already existed.
    1. If not, keep moving end pointer forward.
    2. If the new character is a duplicate one, move the start pointer all the way to pass the duplicate character and pop out all these characters from the hashset.
  3. Repeating step 2 and output the longest substring without dup after finishing the whole string.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public int lengthOfLongestSubstring(String s) {
    if (s == null)
        return 0;
    boolean[] flag = new boolean[256];

    int result = 0;
    int start = 0;
    char[] arr = s.toCharArray();

    for (int i = 0; i < arr.length; i++) {
        char current = arr[i];
        if (flag[current]) {
            result = Math.max(result, i - start);
            // the loop update the new start point
            // and reset flag array
            // for example, abccab, when it comes to 2nd c,
            // it update start from 0 to 3, reset flag for a,b
            for (int k = start; k < i; k++) {
                if (arr[k] == current) {
                    start = k + 1;
                    break;
                }
                flag[arr[k]] = false;
            }
        } else {
            flag[current] = true;
        }
    }

    result = Math.max(arr.length - start, result);

    return result;
}