[LeetCode] 3. Longest Substring Without Repeating Characters

Posted on | In

Problem

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

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Explanation 1

  1. We need to find out the length of substring, so while looping the character of the input string, we can use the current index subtract the start index of the substring. If there is only 1 character, then current index is 0, so we need to subtract -1 to get length of 1 because $0 - -1 = 1$. So we initialize the start index of the substring we are going to find is -1, in this case we define this start index as a variable left. So we can find out the length of the substring using currentIndex - left.

  2. While looping the character of the string, we put the character and its index into a HashMap if we have not seen the character.

  3. If we have seen the character before, then we update the substring’s start index left to the maximum between left and the index of the character we have seen before. Then, in the hashmap, replace its index to the current index.

    1
    2
      0 1 2 3
 "a b b a"
    • When we see the second b, we update left from -1 to 1. Then when we see the second a, we need to update left to the maximum of left and the seen character’s index. In this case, left should be 1 not 0.

  4. In each iteration, we update the maximum length using currentIndex - left.

  5. After we finish the last iteration, we can return the maximum length.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        s.trim();
        if (s.length() == 0) return 0;
        char[] arr = s.toCharArray();
        int left = -1, res = Integer.MIN_VALUE;
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!hm.containsKey(arr[i])) {
                hm.put(arr[i], i);
            } else {
                left = Math.max(left, hm.get(arr[i]));
                hm.put(arr[i], i);
            }
            res = Math.max(res, i-left);
        }
        return res;
    }
}

Explanation 2

  1. We can also solve this problem using sliding window technique. Think of we will maintain a window that contains all unique characters. First initialize windowStart and windowEnd to 0. Also, initialize a hashset to record the window’s unique characters.

  2. Loop the windowEnd from index 0 to the last index of the input string. While the set contains the current iterated character, we remove the window’s left character str[windowStart] and move windowStart 1 step forward, repeat this while loop until the set doesn’t contains the incoming iterated character. Next, we add the iterated character into the set, then calculate the result be max(res, windowEnd - windowStart + 1).

Solution 2

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

        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char cur = s.charAt(windowEnd);
            while (set.contains(cur)) {
                char windowLeft = s.charAt(windowStart);
                set.remove(windowLeft);
                windowStart += 1;
            }
            set.add(cur);
            res = Math.max(res, windowEnd - windowStart + 1);
        }

        return res;
    }
}