Light Dark

3. Longest Substring Without Repeating Characters

Back to Certificates

Problem Description

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

Example:

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

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

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.

Solution Approach

We can use a sliding window approach to solve this problem:

  1. Maintain a set to track characters in current window
  2. Use two pointers (left and right) to represent the window
  3. Expand the window (right pointer) as long as no duplicates are found
  4. When a duplicate is found, shrink window from left until the duplicate is removed
  5. Keep track of the maximum window size seen so far

Time Complexity: O(n) where n is the length of the string. Each character is processed at most twice (once by right pointer, once by left pointer).

Space Complexity: O(min(m, n)) where m is the size of the character set. In the worst case, the set may contain all characters in the string.

Python Implementation:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_len = 0
        
        for right, ch in enumerate(s):
            # If character is already in our window, shrink window from left
            while ch in seen:
                seen.remove(s[left])
                left += 1
                
            # Add current character to window
            seen.add(ch)
            
            # Update maximum length
            max_len = max(max_len, right - left + 1)
            
        return max_len