Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters. This is LeetCode 3.

Example 1
Input: s = "abcabcbb"
Output: 3
Explanation: "abc".
Example 2
Input: s = "bbbbb"
Output: 1
Explanation: "b".
Example 3
Input: s = "pwwkew"
Output: 3
Explanation: "wke". "pwke" does not count: it is a subsequence, not a substring.

How to Think About It

Step 1: The simple way

Check every substring for repeats: O(n³), or O(n²) with a set. Too slow for 5 × 104 characters.

Step 2: A window with no repeats

Keep a window s[left .. right] that never contains a repeated character. Move right forward one character at a time. If the new character is not already in the window, the window simply grows.

Step 3: Jump left past the earlier copy

If s[right] is already in the window, every window that still contains the earlier copy is broken. So left moves to one past that copy. Remember the last index of every character in an array lastSeen, and the jump is a single step:

left = lastSeen[c] + 1

Step 4: Ignore copies that already left

A character's last index may be from before left, outside the window. Then it is not a repeat, and left must not move backwards. That is why the code checks lastSeen[c] >= left. In "abba", when the second a arrives, the first a at index 0 is already outside the window that starts at 2.

Walkthrough

s = "abcabcbb".

right (char)Earlier copy in window?left afterWindowBest
0 (a)no0a1
1 (b)no0ab2
2 (c)no0abc3
3 (a)yes, at 01bca3
4 (b)yes, at 12cab3
5 (c)yes, at 23abc3
6 (b)yes, at 45cb3
7 (b)yes, at 67b3

Java Solution

An int[128] filled with -1 covers all ASCII characters, which includes letters, digits, symbols and spaces.

Java
import java.util.Arrays;

public class LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String s) {
        int[] lastSeen = new int[128];        // last index of each character, or -1
        Arrays.fill(lastSeen, -1);
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen[c] >= left) {
                left = lastSeen[c] + 1;       // jump past the earlier copy of c
            }
            lastSeen[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));   // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));      // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));     // 3
        System.out.println(lengthOfLongestSubstring("abba"));       // 2
    }
}

The original implementation, LongestSubstringWithoutRepeatingCharacters.java, is on GitHub.

Complexity

  • Time: O(n): one pass, and left only jumps forward.
  • Space: O(1): a fixed array of 128 entries.

The jump-to-last-index trick also appears in Maximum Erasure Value. Sliding Window Basics covers the general template.