10.1 Longest Substring Without Repeating Characters

10.1.1 Problem Metadata

10.1.2 Description

Given a string s, return the length of the longest substring that contains no repeated characters.

10.1.3 Examples

Input: s = "abcabcbb"
Output: 3

Input: s = "bbbbb"
Output: 1

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke"; "pwke" is not valid because it is not a contiguous substring.

10.1.4 Constraints

  • 0 <= s.length <= 5 * 10^4
  • s consists of Englc-lish letters, digits, symbols, and spaces

10.1.5 Solution - Sliding Window Set

10.1.5.1 Walkthrough

Maintain a sliding window [left, right] backed by a hash set of characters currently in the window. Expand right while characters are unique, updating the maximum window length. Whenever a duplicate appears, shrink from the left until the duplicate is removed. This ensures each character enters and leaves the window at most once.

Key Concept - Window Length Calculation: - The window spans from index left to index right (inclusive) - Window length formula: right - left + 1 - Example: For window from index 2 to index 5, length = 5 - 2 + 1 = 4 characters

Visual Example with s = "abcabcbb":

Initial state: left = 0, right starts at 0, best = 0, seen = {}

Step 1: right = 0, char = 'a'
  String: [a] b c a b c b b
          ↑
       left,right
  seen = {a}
  Window length = 0 - 0 + 1 = 1
  best = 1

Step 2: right = 1, char = 'b'
  String: [a b] c a b c b b
          ↑   ↑
        left right
  seen = {a, b}
  Window length = 1 - 0 + 1 = 2
  best = 2

Step 3: right = 2, char = 'c'
  String: [a b c] a b c b b
          ↑     ↑
        left  right
  seen = {a, b, c}
  Window length = 2 - 0 + 1 = 3
  best = 3

Step 4: right = 3, char = 'a' (DUPLICATE!)
  String: a b c [a] b c b b
                 ↑
               right
  'a' is in seen, shrink from left:
    - Remove 'a' at left=0, left becomes 1
    - seen = {b, c}
  Now add 'a' back:
  String: a [b c a] b c b b
            ↑     ↑
          left  right
  seen = {b, c, a}
  Window length = 3 - 1 + 1 = 3
  best = 3

Step 5: right = 4, char = 'b' (DUPLICATE!)
  String: a b c [a b] c b b
                     ↑
                   right
  'b' is in seen, shrink from left:
    - Remove 'b' at left=1, left becomes 2
    - seen = {c, a}
  Now add 'b' back:
  String: a b [c a b] c b b
              ↑     ↑
            left  right
  seen = {c, a, b}
  Window length = 4 - 2 + 1 = 3
  best = 3

Step 6: right = 5, char = 'c' (DUPLICATE!)
  String: a b c [a b c] b b
                       ↑
                     right
  'c' is in seen, shrink from left:
    - Remove 'c' at left=2, left becomes 3
    - seen = {a, b}
  Now add 'c' back:
  String: a b c [a b c] b b
                ↑     ↑
              left  right
  seen = {a, b, c}
  Window length = 5 - 3 + 1 = 3
  best = 3

Step 7: right = 6, char = 'b' (DUPLICATE!)
  String: a b c a [b c b] b
                         ↑
                       right
  'b' is in seen, shrink from left:
    - Remove 'a' at left=3, left becomes 4
    - 'b' still in seen
    - Remove 'b' at left=4, left becomes 5
    - seen = {c}
  Now add 'b' back:
  String: a b c a b [c b] b
                    ↑   ↑
                  left right
  seen = {c, b}
  Window length = 6 - 5 + 1 = 2
  best = 3

Step 8: right = 7, char = 'b' (DUPLICATE!)
  String: a b c a b c [b b]
                         ↑
                       right
  'b' is in seen, shrink from left:
    - Remove 'c' at left=5, left becomes 6
    - 'b' still in seen
    - Remove 'b' at left=6, left becomes 7
    - seen = {}
  Now add 'b' back:
  String: a b c a b c b [b]
                        ↑ ↑
                    left,right
  seen = {b}
  Window length = 7 - 7 + 1 = 1
  best = 3

Final result: 3

Key Takeaways: 1. The window [left, right] always contains unique characters 2. When a duplicate is found, we shrink from the left until the duplicate is removed 3. right - left + 1 gives the current window size because both indices are inclusive 4. We track the maximum window size seen throughout the process

10.1.5.2 Analysis

  • Time Complexity: O(n) because each character is processed at most twice
  • Space Complexity: O(min(n, alphabet)) for the sliding-set storage

10.1.5.3 Implementation Steps

  1. Initialize Set<Character> seen, left = 0, best = 0.
  2. Iterate right over the string.
  3. While s[right] is already in seen, remove s[left] and increment left.
  4. Add s[right], update best = max(best, right - left + 1).
  5. Return best.

10.1.5.4 Code - Java

public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (seen.contains(c)) {
            seen.remove(s.charAt(left));
            left++;
        }
        seen.add(c);
        best = Math.max(best, right - left + 1);
    }

    return best;
}