Longest Substring Without Repeating Characters

MediumString Hash Table Sliding Window

A typing tutor rewards variety: it looks for the longest stretch of a player's keystrokes in which no key is pressed twice. The keystrokes arrive as a string s, one character per key press, and letters, digits, symbols and the space bar all count as keys.

Return the length of the longest contiguous block of s whose characters are all different. An empty string gives 0.

Example 1

Input: s = "racecar"
Output: 4

Explanation: "race" (and also "ecar") has four different characters; every block of five repeats a letter.

Example 2

Input: s = "1 2 3"
Output: 3

Explanation: Spaces count as keys: "1 2" has three different characters, and extending it would repeat the space.

Example 3

Input: s = ""
Output: 0

Constraints

s is between 0 and 50,000 characters long.
s can contain 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