Longest Substring Without Repeating Characters

Mediumsliding-windowhash-tablestring
Category: Sliding Window
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg
LeetCode →NeetCode →

Approach

Longest Substring Without Repeating Characters

Problem Statement

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

Examples

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.

Intuition

We need to find the longest window (substring) where all characters are unique. The key insight is to use a sliding window with:

  • Expand: Add characters to the window (move right pointer)
  • Contract: Remove characters when we find a duplicate (move left pointer)
  • Track: Use a set/map to detect duplicates in O(1) time

Pattern Recognition

This is a classic Sliding Window problem with:

  • Variable window size
  • Constraint: all characters in window must be unique
  • Need to track characters seen in current window
  • Optimize: O(n) time instead of O(n²) brute force

Approach

Sliding Window with HashSet:

  1. Initialize:

    • left = 0, right = 0 (window boundaries)
    • charSet = empty set (tracks characters in current window)
    • maxLength = 0

  2. Expand Window (move right):

    • While right < s.length:
      • If s[right] not in charSet:
        • Add s[right] to charSet
        • Update maxLength = max(maxLength, right - left + 1)
        • Move right++
      • Else (duplicate found):
        • Remove s[left] from charSet
        • Move left++ (contract window)

  3. Return maxLength

Edge Cases

  • Empty string (length 0)
  • Single character (length 1)
  • All characters unique (length = string length)
  • All characters same (length = 1)
  • String with spaces or special characters

Complexity Analysis

  • Time Complexity: O(n) where n is the length of string
    • Each character visited at most twice (once by right, once by left)
    • HashSet operations (add, remove, contains) are O(1)
  • Space Complexity: O(min(n, k)) where k is the character set size
    • HashSet stores at most all unique characters
    • For ASCII: O(128), for Unicode: O(256), worst case: O(n)

Solution

java
1class Solution {
2    public int lengthOfLongestSubstring(String s) {
3        Set<Character> charSet = new HashSet<>();
4        int left = 0;
5        int maxLength = 0;
6
7        for (int right = 0; right < s.length(); right++) {
8            // Contract window while duplicate exists
9            while (charSet.contains(s.charAt(right))) {
10                charSet.remove(s.charAt(left));
11                left++;
12            }
13
14            // Add current character to window
15            charSet.add(s.charAt(right));
16
17            // Update max length
18            maxLength = Math.max(maxLength, right - left + 1);
19        }
20
21        return maxLength;
22    }
23}
24
Loading visualizer...