We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Substring Without Repeating Characters

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires identifying the longest contiguous substring with all unique characters.
  • A sliding window approach can be employed to dynamically adjust the current substring being evaluated.
  • A hash table (or dictionary) can be used to track the characters and their most recent indices for efficient look-up.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(min(n, m)), where m is the size of the character set (e.g., 26 for lowercase English letters).

Solution

The solution employs a sliding window technique along with a hash table to keep track of characters and their indices. The idea is to maintain a window of characters that are currently unique. As we iterate through the string, we expand the window by adding characters to it. If we encounter a duplicate character, we shift the start of the window to the right of the previous occurrence of that character.

Code Solutions

def length_of_longest_substring(s: str) -> int:
    char_index_map = {}
    left = 0  # Start of the sliding window
    max_length = 0  # Maximum length of substring found
    
    for right in range(len(s)):
        if s[right] in char_index_map:
            # Move the left pointer to the right of the last occurrence
            left = max(left, char_index_map[s[right]] + 1)
        
        # Update the last seen index of the character
        char_index_map[s[right]] = right
        
        # Calculate the max length of the substring
        max_length = max(max_length, right - left + 1)
    
    return max_length
← Back to All Questions