Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters using a sliding window and hash map to track state efficiently.

hash table string sliding window

Problem Statement

Given a string s, determine the length of the longest contiguous substring that contains no repeating characters. Each character in the string may include letters, digits, symbols, or spaces. The challenge is to efficiently manage state as the substring expands and contracts while scanning from left to right to identify valid substrings and update the maximum length encountered.

For example, given s = "abcabcbb", the longest substring without duplicates is "abc" with length 3. Similarly, for s = "pwwkew", the correct substring is "wke" with length 3, highlighting that subsequences are invalid and only continuous substrings count. Constraints include strings up to length 50,000 and all ASCII characters.

Examples

Example 1

Input: s = "abcabcbb"

Output: 3

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

Example 2

Input: s = "bbbbb"

Output: 1

The answer is "b", with the length of 1.

Example 3

Input: s = "pwwkew"

Output: 3

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.

Constraints

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

Solution Approach

Sliding Window with Hash Map Tracking

Use two pointers to define the current window and a hash map to track characters and their latest indices. Expand the right pointer while characters are unique, and when a duplicate is found, move the left pointer to one past the previous index of the duplicate. Update the maximum substring length at each step. This method avoids checking all substrings, providing linear scanning while keeping track of repeated characters dynamically, which is ideal for the sliding window pattern.

Dynamic Window Shrinking on Duplicate Detection

When a duplicate character is detected in the current window, shrink the window from the left until the duplicate is removed. Adjust the starting pointer carefully to skip past the previous occurrence, ensuring that no characters are counted twice. This maintains correctness while still traversing each character only once. Properly handling this adjustment prevents off-by-one errors and ensures the substring remains valid, a key failure mode in naive sliding window implementations that do not track character indices.

Max Length Calculation and Edge Cases

Maintain a variable to track the maximum length encountered during window traversal. After each right pointer movement or window adjustment, compute the current window size and update the maximum if larger. Edge cases include empty strings, single-character strings, or strings with all duplicates. Correct handling of these ensures accurate output. This step ties together the sliding window mechanics and hash map tracking, making sure the algorithm efficiently computes the longest substring without repeated characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Using the sliding window with a hash map, each character is visited at most twice, giving a time complexity of O(n). Space complexity is O(min(n,m)) where m is the character set size, due to storing character indices. The provided approach efficiently manages state to track duplicates dynamically, matching the expected linear time and moderate space requirements.

What Interviewers Usually Probe

Do you recognize the need to update the start pointer when encountering duplicates?
Can you explain why a hash map is used instead of nested loops for substring checks?
Will you handle edge cases like empty strings or strings with all identical characters?

Common Pitfalls or Variants

Common pitfalls

Failing to move the left pointer past the previous duplicate, leading to incorrect max length calculations.
Using nested loops to generate substrings instead of a sliding window, resulting in TLE for large inputs.
Misinterpreting subsequences as substrings, which causes incorrect results like including non-contiguous characters.

Follow-up variants

Find the longest substring containing at most k distinct characters, extending the sliding window pattern.
Return the actual longest substring without repeating characters instead of just its length.
Compute the number of substrings without repeating characters instead of the maximum length, requiring cumulative counting.

FAQ

What is the optimal approach for Longest Substring Without Repeating Characters?

Use a sliding window with a hash map to track the last index of each character. Move the start pointer when duplicates appear and update max length dynamically.

Why is the sliding window pattern essential for this problem?

It allows linear traversal while maintaining a valid substring without duplicates, avoiding the inefficiency of checking all possible substrings.

How should I handle edge cases like empty or single-character strings?

For empty strings return 0. For single-character strings return 1. The algorithm naturally handles these when initializing pointers and max length.

Can subsequences be considered instead of substrings?

No, only contiguous characters form valid substrings. Non-contiguous sequences like "pwke" in "pwwkew" are invalid for this problem.

What common mistakes occur when updating the window on duplicates?

Common errors include not moving the left pointer correctly past the previous duplicate, double-counting characters, or miscalculating the current window size.

terminal

Solution

Solution 1: Sliding Window

We can use two pointers $l$ and $r$ to maintain a sliding window that always satisfies the condition of having no repeating characters within the window. Initially, both $l$ and $r$ point to the first character of the string. We use a hash table or an array of length $128$ called $\textit{cnt}$ to record the number of occurrences of each character, where $\textit{cnt}[c]$ represents the number of occurrences of character $c$.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = Counter()
        ans = l = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 1:
                cnt[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

Continue Practicing

#30 substring with concatenation of all words #76 minimum window substring #187 repeated dna sequences