Longest Substring Without Repeating Characters - Video Solutions

Problem Overview: Given a string s, return the length of the longest substring that contains no repeating characters. The substring must be continuous, so you cannot skip characters or reorder them.

Approach 1: Brute Force (O(n^3) time, O(min(n, k)) space)

Generate every possible substring and check if it contains duplicate characters. For each starting index i, extend the substring to j and verify uniqueness using a set or frequency array. The duplicate check itself scans the substring, which pushes the complexity to O(n^3). This approach is rarely used in production but helps you reason about the problem before introducing optimizations related to string processing.

Approach 2: Sliding Window with Hash Set (O(n) time, O(k) space)

Use the sliding window pattern with two pointers left and right. Expand the window by moving right while inserting characters into a set. If a duplicate appears, shrink the window by moving left and removing characters until the duplicate is removed. Each character is added and removed at most once, giving O(n) time. The set stores the current window's characters, so space complexity is O(k), where k is the character set size.

Approach 3: Optimized Sliding Window with Hash Map (O(n) time, O(min(n, k)) space)

This is the most common interview solution. Instead of shrinking the window one step at a time, store the last seen index of each character in a hash table. When you encounter a duplicate, jump the left pointer directly to lastIndex + 1. This avoids repeated removals and keeps the window valid in constant time. You still iterate through the string once, so the time complexity remains O(n), while the hash map stores at most one entry per character.

Recommended for interviews: Interviewers expect the optimized sliding window with a hash map. Starting with the brute force idea shows you understand the constraint of unique characters. Transitioning to the sliding window demonstrates algorithmic maturity and familiarity with common patterns used in string and two-pointer problems.