LeetCode 3. Longest Substring Without Repeating Characters

Question

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

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

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

Solution

Sliding window is an optimization for brutal force search. When searching substrings that satisfy certain conditions, we do not have to examine every substring. In some cases, we can end up some search paths early and try another direction, which is similar to pruning in DFS.

Take the following string as an example. It is meaningless to check substrings that start with ‘a’, ‘b’, ‘c’ and the first ‘5’ because they will definitely include repeating ‘5’ if they have a larger or the same length.

// brutal force, O(n^2)
public int lengthOfLongestSubstring0(String s) {
    int len = s.length();
    int maxSubLen = 0;
    Set<Character> set = new HashSet<>();
    // i, j are the left and right end (inclusive) of a substring
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            char c = s.charAt(j);
            if (set.contains(c)) {
                break;
            } else {
                set.add(c);
                maxSubLen = Math.max(maxSubLen, j - i + 1);
            }
        }
        set.clear();
    }
    return maxSubLen;
}

// sliding window, O(n)
public int lengthOfLongestSubstring1(String s) {
    int len = s.length();
    int maxSubLen = 0;
    int left = 0, right = 0;
    // character -> frequency in the current substring
    Map<Character, Integer> map = new HashMap<>();
    while (left < len && right < len) {
        char cright = s.charAt(right);
        while (map.getOrDefault(cright, 0) > 0) {
            char cleft = s.charAt(left);
            map.put(cleft, map.get(cleft) - 1);
            left++;
        }
        map.put(cright, 1);
        maxSubLen = Math.max(maxSubLen, right - left + 1);
        right++;
    }
    return maxSubLen;
}

// optimized sliding window, O(n)
public int lengthOfLongestSubstring2(String s) {
    int len = s.length();
    int maxSubLen = 0;
    int left = 0, right = 0;
    // character -> last index of this character
    Map<Character, Integer> map = new HashMap<>();
    while (left < len && right < len) {
        char cright = s.charAt(right);
        if (map.containsKey(cright)) {
            // when left end moving forward, we do not remove kv pairs from map
            // only if the last index of cright is within the range of current substring
            // we move left forward
            left = Math.max(left, map.get(cright) + 1);
        }
        map.put(cright, right);
        maxSubLen = Math.max(maxSubLen, right - left + 1);
        right++;
    }
    return maxSubLen;
}