Skip to main content
Talentd

Longest Substring Without Repeating Characters - Solution & Explanation

MediumHash TableStringSliding Window22 min readAsked at: Amazon, Microsoft, Apple +102
Practice this problem

Problem Statement

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

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: 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.

Approach Overview

Problem Overview: Given a string s, return the length of the longest substring that contains no repeating characters. The substring must be continuous, so you cannot skip characters or reorder them.

Approach 1: Brute Force (O(n^3) time, O(min(n, k)) space)

Generate every possible substring and check if it contains duplicate characters. For each starting index i, extend the substring to j and verify uniqueness using a set or frequency array. The duplicate check itself scans the substring, which pushes the complexity to O(n^3). This approach is rarely used in production but helps you reason about the problem before introducing optimizations related to string processing.

Approach 2: Sliding Window with Hash Set (O(n) time, O(k) space)

Use the sliding window pattern with two pointers left and right. Expand the window by moving right while inserting characters into a set. If a duplicate appears, shrink the window by moving left and removing characters until the duplicate is removed. Each character is added and removed at most once, giving O(n) time. The set stores the current window's characters, so space complexity is O(k), where k is the character set size.

Approach 3: Optimized Sliding Window with Hash Map (O(n) time, O(min(n, k)) space)

This is the most common interview solution. Instead of shrinking the window one step at a time, store the last seen index of each character in a hash table. When you encounter a duplicate, jump the left pointer directly to lastIndex + 1. This avoids repeated removals and keeps the window valid in constant time. You still iterate through the string once, so the time complexity remains O(n), while the hash map stores at most one entry per character.

Recommended for interviews: Interviewers expect the optimized sliding window with a hash map. Starting with the brute force idea shows you understand the constraint of unique characters. Transitioning to the sliding window demonstrates algorithmic maturity and familiarity with common patterns used in string and two-pointer problems.

Approach 1: Sliding Window Approach

This approach uses a two-pointer technique (often called a sliding window) to efficiently find the longest substring without repeating characters. The idea is to keep moving a start pointer to the right, while expanding the end pointer, ensuring all characters between the two pointers are unique.

The code uses an integer array index of size 128 to store the last index + 1 of each character. We iterate end over the string, and if the character has appeared before, we move the start pointer to the right of the previous index. Then, update the maxLen if the current substring length is greater than maxLen.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice, once by the start pointer and once by the end pointer.
Space Complexity: O(1), since we use a fixed array of size 128 for ASCII characters.

Try this approach in the editor →

Approach 2: 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 cnt to record the number of occurrences of each character, where cnt[c] represents the number of occurrences of character c.

Next, we move the right pointer r one step at a time. Each time we move it, we increment the value of cnt[s[r]] by 1, and then check if the value of cnt[s[r]] is greater than 1 within the current window [l, r]. If it is greater than 1, it means there are repeating characters within the current window, and we need to move the left pointer l until there are no repeating characters within the window. Then, we update the answer ans = max(ans, r - l + 1).

Finally, we return the answer ans.

The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma represents the character set, and the size of \Sigma is 128.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPSwiftKotlinC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Swift

Kotlin

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice, once by the start pointer and once by the end pointer.
Space Complexity: O(1), since we use a fixed array of size 128 for ASCII characters.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force (check every substring)O(n^3)O(min(n, k))Conceptual understanding or very small inputs
Sliding Window with Hash SetO(n)O(k)General solution using two pointers and window expansion/shrinking
Optimized Sliding Window with Hash MapO(n)O(min(n, k))Preferred interview approach with direct index jumps

Video Solution

Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 856,354 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Substring Without Repeating Characters easy or hard?
The problem is usually classified as Medium difficulty. The challenge comes from recognizing the sliding window pattern and handling duplicate characters efficiently while maintaining a valid substring window.
Longest Substring Without Repeating Characters Python/Java solution
Most Python and Java solutions implement the sliding window with a dictionary or HashMap that stores character indices. The algorithm iterates through the string once, updates the window start when duplicates appear, and tracks the maximum window length.
How to solve Longest Substring Without Repeating Characters in O(n)?
Maintain a sliding window using two pointers and a hash map storing the last index of each character. As you iterate through the string, update the left pointer whenever a duplicate appears inside the current window. This prevents rescanning characters and keeps the algorithm linear.
What is the best approach for Longest Substring Without Repeating Characters?
The optimized sliding window with a hash map is the best approach. It tracks the last seen index of each character and moves the left pointer directly past duplicates. This processes the string in one pass with O(n) time and O(min(n, k)) space, where k is the character set size.
Is Longest Substring Without Repeating Characters asked at Google/Amazon/Meta?
Longest Substring Without Repeating Characters frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests sliding window patterns, hash table usage, and efficient string processing, which are common themes in coding interviews.
What data structure is used in Longest Substring Without Repeating Characters?
The typical implementation uses a hash table (hash map) or hash set along with two pointers. The hash structure tracks characters currently in the window or their most recent index, enabling constant-time duplicate checks.
What is the time complexity of Longest Substring Without Repeating Characters?
The optimal solution runs in O(n) time using a sliding window. Each character is processed at most once while the window expands and occasionally shifts forward. Space complexity is O(min(n, k)) due to the hash table storing last seen positions.

Ready to solve this problem?

Practice Longest Substring Without Repeating Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Complete Subarrays in an Array

Next

Find Longest Special Substring That Occurs Thrice I