How to Solve Longest Substring Without Repeating Characters

This problem requires identifying the longest substring without duplicates using a sliding window and hash map to track characters. Move the window forward, updating the start when duplicates are found. Maintain a maximum length during traversal to return the final result, ensuring O(n) time complexity and efficient state tracking for all character types.

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

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.

How GhostInterview Helps

• Capture or screenshot input string, highlighting positions and duplicates for visual understanding.
• Provide answer path with step-by-step sliding window updates and clear explanation of time O(n) and space O(min(n,m)) complexities.
• Support screen-share workflows showing the dynamic window, hash map state, and captured layers during traversal for interactive debugging.

Topic Pages

• Hash Table
• String
• Sliding Window

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.