Longest Substring Without Repeating Characters

Sliding WindowHash Map

MediumLeetCode #3

25 min

Problem Statement

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

Example

Example 1:

Input: s = "abcabcbb"

s: "abcabcbb"

Output: 3

The answer is "abc", with the length of 3.

Solution

The problem can be solved efficiently using a sliding window approach with a hash map. The hash map stores the most recent index of each character. The left pointer of the window only moves when a repeating character is found.

Algorithm Steps

Initialize a hash map `charIndexMap`, a `maxLength` to 0, and a left pointer `l` to 0.
Iterate through the string with a right pointer `r`.
If the character `s[r]` is already in the hash map and its index is within the current window (i.e., `charIndexMap[s[r]] >= l`), move the left pointer `l` to the right of the last occurrence of `s[r]`.
Update the character's index in the hash map to the current index `r`.
Update `maxLength` with the length of the current window (`r - l + 1`).

Longest Substring Without Repeating Characters

Sliding Window with Hash Map

Progress1 / 1

Ready to start the visualization

Hash Map (char: index)

Max Length

Longest Substring Without Repeating Characters Solution


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in char_set:
                char_set.remove(s[l])
                l += 1
            char_set.add(s[r])
            res = max(res, r - l + 1)
        return res