18. Longest Substring Without Repeating Characters

MediumString Hash Table Sliding Window

Given a string s, return the length of the longest substring (a contiguous block of characters) in which no character appears more than once.

Example 1

Input: s = "abcdbef"
Output: 5

Explanation: "abcd" stops at the second b; starting just after the first b, "cdbef" has 5 distinct characters.

Example 2

Input: s = "aaaa"
Output: 1

Example 3

Input: s = ""
Output: 0

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces

💡 Hint 1

Keep a window [left, right] that never contains a repeated character, and grow it one character at a time.

💡 Hint 2

When the new character already occurs inside the window, the window must start just after that earlier occurrence.

💡 Hint 3

Remember the last index of every character so you can jump left directly instead of shrinking one step at a time. Never move left backwards.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use a sliding window and a map from each character to the index where it was last seen. Move right across the string. If s[right] was last seen at an index >= left, it is inside the window, so jump left to one past that index. Then record s[right]'s new position and update the best length right - left + 1. left only moves forward, so each character is processed once.

Time O(n)Space O(min(n, alphabet size))

function lengthOfLongestSubstring(s) {
  const last = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const prev = last.get(s[right]);
    if (prev !== undefined && prev >= left) left = prev + 1;
    last.set(s[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last[c] >= left) left = last[c] + 1;
            last[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit