3. Longest Substring Without Repeating Characters

The word “substring” is the whole hint: the answer is contiguous, so a window that slides across the string — growing on the right, shrinking on the left when a character repeats — captures every candidate in one pass. The interesting part is how you shrink.

Question

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

• Example1

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

• Example2

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

• Example3

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 * 10^4$
  • s consists of English letters, digits, symbols and spaces.

The window, in one rule

Keep a window [left, right] that holds only distinct characters. Push right forward one step at a time. The moment the new character is already inside the window, pull left forward until it isn’t — then record the window length. Every character enters and leaves the window at most once, which is what makes it a single sliding window pass instead of an $O(n^2)$ recheck of every start point.

Answer

// Sliding Window with HashSet
// TC: O(n)
// SC: O(n)
public int lengthOfLongestSubstring(String s) {
    if (s == null) return 0;
    Set<Character> set = new HashSet<>();
    int left = 0;
    int maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Two ways to shrink: step vs jump

The set version above shrinks by stepping — on a repeat it removes characters from the left one at a time until the duplicate clears. That’s correct and still $O(n)$ overall (each character is removed at most once), but every removal is a separate loop turn.

The optimized version skips the stepping entirely. Instead of a set, it stores the last position of each character, so on a repeat it can jump left straight past the previous copy in one move:

// Sliding Window with int[128] (optimized — jumps left pointer directly)
// TC: O(n)
// SC: O(1)
public int lengthOfLongestSubstring(String s) {
    if (s == null) return 0;
    int[] index = new int[128]; // last seen index + 1 for each char
    int result = 0;
    for (int left = 0, right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, index[c]);
        result = Math.max(result, right - left + 1);
        index[c] = right + 1;
    }
    return result;
}

The Math.max(left, index[c]) is the line that earns the speedup, and the line people get wrong. index[c] holds one past where c last sat — the code stores right + 1 — so it’s exactly where the window should resume, just after that copy. But an old copy might sit behind the current left, already outside the window, and jumping straight there would drag left backward and start counting duplicates again. Taking the max pins left so it only ever moves forward. The int[128] also fixes the space at $O(1)$: one slot per ASCII code, no matter how long the string is.

Complexity and edge cases

Both versions are $O(n)$ time. Space is where they differ — $O(\min(n, 128))$ for the set, $O(1)$ for the array. A few inputs worth a mental check:

• Empty string — the loop never runs, so you get 0.
• All identical ("bbbbb") — the window can never exceed one character, so 1.
• All distinct ("abcdef") — the window never shrinks and the answer is the full length.

For a harder cousin where the window shrinks to a minimum instead of staying duplicate-free, see Minimum Window Substring — same machinery, stricter validity rule.

References

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