Longest Substring Without Duplicates

Tags

Longest Substring Without Duplicates

Category

Strings

Difficulty

Medium

Problem Statement

Given a string, find the length of the longest substring that contains no duplicate characters. Return the longest such substring.

Intuition

We can use a sliding window approach where the window always contains unique characters. As we expand the window to the right, if we encounter a character already in the window, we shrink the window from the left until the duplicate is removed. A hash map tracking the last seen index of each character allows us to jump the left pointer directly to the correct position, avoiding character-by-character shrinking.

Approach

  1. Initialize a hash map to store the last seen index of each character.
  2. Maintain a left pointer starting at index 0 and track the best substring found.
  3. Iterate with a right pointer through the string: a. If the current character exists in the map and its last seen index is >= left, move left to (last seen index + 1). b. Update the map with the current character's index. c. If (right - left + 1) exceeds the current best length, update the best substring boundaries.
  4. Return the longest substring found.

Pseudocode

function longestSubstringWithoutDuplicates(string):
    lastSeen = {}
    left = 0
    bestStart = 0
    bestLength = 0

    for right from 0 to len(string) - 1:
        char = string[right]
        if char in lastSeen and lastSeen[char] >= left:
            left = lastSeen[char] + 1
        lastSeen[char] = right
        currentLength = right - left + 1
        if currentLength > bestLength:
            bestLength = currentLength
            bestStart = left

    return string[bestStart : bestStart + bestLength]

Time & Space Complexity

  • Time: O(n) where n is the length of the string. Each character is visited at most once by the right pointer, and the left pointer only moves forward.
  • Space: O(min(n, a)) where a is the size of the character alphabet. The hash map stores at most one entry per unique character.

Key Insights

  • The sliding window never backtracks: both pointers only move forward, ensuring linear time.
  • Storing the last seen index allows the left pointer to jump directly past the duplicate, rather than incrementing one position at a time.
  • The condition lastSeen[char] >= left is critical; without it, we might react to a character that is outside the current window.

Edge Cases

  • Empty string: return an empty string.
  • String with all identical characters: the longest substring has length 1.
  • String with all unique characters: the entire string is the answer.
  • Single character string: return that character.
  • Duplicates at the very beginning and end of the string.

Linked mentions