Log inSign up
mediumleetcodeNot Started

Longest Substring Without Repeating Characters

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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

Example 1 · Example:

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

Example 2 · Example:

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

Example 3 · Example:

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master variable sliding window techniques with dynamic bounds.
  • Implement O(1) index jump transitions.
  • Handle all ASCII characters including whitespace and punctuation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the longest/shortest contiguous substring with unique elements or constraint thresholds.
  • Tracking the most recent occurrences of elements in streams.

Algorithmic Decision Tree:

  • Dynamic Sliding Window
  • Last Seen Index Map Jump

Connected Patterns:

Longest Repeating Character ReplacementMinimum Window SubstringMax Consecutive Ones III

1. Nested Checking All Substrings

Intuition

For every start index i from 0 to n - 1, and every end index j from i to n - 1: verify if all characters in s[i...j] are distinct using a hash set. Track the maximum length found.

When to apply: Basic naive conceptual baseline.

Algorithm

  1. Initialize maxLen = 0.
  2. Loop i from 0 to n - 1:
  3. Initialize set.
  4. Loop j from i to n - 1:
  5. If set.contains(s[j]): break.
  6. set.add(s[j])
  7. maxLen = max(maxLen, j - i + 1)
  8. Return maxLen.

Nested Checking All Substrings

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a, b, c, b, b]
Current operationSTEP 1 OF 6
Observation: Outer pointer $i = 0$
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
b
c
b
b
0
↑ i=0 ('a')
1
2
↑ j=2 ('c')
3
4
5
6
7
Variables at this step
i
0
uniqueSubstring
abc
len
3
maxLen
3
Check / comparison
Starting at i=0, expand j: 'a' (len 1), 'ab' (len 2), 'abc' (len 3).
Decision / next transition
At j=3, char is 'a' (duplicate). Stop expansion from i=0. maxLen = 3.
Why this step matters

Observation: Outer pointer i = 0. Expand inner pointer j: characters 'a', 'b', 'c' are all unique.

Decision: At j = 3, character 'a' repeats. Expansion stops; update maxLen = 3.

Invariant: A substring without duplicates cannot contain any character with frequency > 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_set>
4#include <algorithm>
5
6class Solution {
7public:
8 int lengthOfLongestSubstring(std::string s) {
9 int n = s.size();
10 int maxLen = 0;
11 for (int i = 0; i < n; ++i) {
12 std::unordered_set<char> seen;
13 for (int j = i; j < n; ++j) {
14 if (seen.count(s[j])) break;
15 seen.insert(s[j]);
16 maxLen = std::max(maxLen, j - i + 1);
17 }
18 }
19 return maxLen;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << sol.lengthOfLongestSubstring("abcabcbb") << std::endl; // 3
26 std::cout << sol.lengthOfLongestSubstring("bbbbb") << std::endl; // 1
27 std::cout << sol.lengthOfLongestSubstring("pwwkew") << std::endl; // 3
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N^2) — Tests all N * (N + 1) / 2 substring pairs.
  • Space complexity: O(M) where M is distinct characters count

Why Brute Force Doesn't Scale:

Directly jumping the left pointer reduces inner while loop steps to O(1).

Using a static 256-element array allocates fixed stack memory with O(1) space complexity.

2. Sliding Window with Hash Set (2N Steps)

Intuition

Maintain a hash set seen representing current window characters. Loop right from 0 to n - 1: while seen.contains(s[right]), remove s[left] from seen and increment left++. Add s[right] to seen and update maxLen = max(maxLen, right - left + 1).

When to apply: When explaining the foundational sliding window principle.

Algorithm

  1. Initialize seen = set(), left = 0, maxLen = 0.
  2. For right from 0 to n - 1:
  3. While seen.contains(s[right]):
  4. seen.remove(s[left])
  5. left++
  6. seen.add(s[right])
  7. maxLen = max(maxLen, right - left + 1)
  8. Return maxLen.

Sliding Window with Hash Set (2N Steps)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a, b, c, b, b]
Current operationSTEP 1 OF 6
Observation: Window starts at [0
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
b
c
b
b
0
↑ L=0, R=0 ('a')
1
2
3
4
5
6
7
Variables at this step
L
0
R
0
set
["a"]
maxLen
1
Check / comparison
Add 'a' to set: { 'a' }. Window length = 1.
Decision / next transition
maxLen = 1. Advance R to 1.
Why this step matters

Observation: Window starts at [0..0]. Add 'a' to hash set.

Decision: Unique characters maintained; maxLen = 1. Expand R.

Invariant: Hash set stores exactly the unique characters currently within [L..R].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_set>
4#include <algorithm>
5
6class Solution {
7public:
8 int lengthOfLongestSubstring(std::string s) {
9 int n = s.size();
10 std::unordered_set<char> seen;
11 int left = 0, maxLen = 0;
12
13 for (int right = 0; right < n; ++right) {
14 while (seen.count(s[right])) {
15 seen.erase(s[left]);
16 left++;
17 }
18 seen.insert(s[right]);
19 maxLen = std::max(maxLen, right - left + 1);
20 }
21 return maxLen;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.lengthOfLongestSubstring("abcabcbb") << std::endl; // 3
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2N) = O(N) — Each character is inserted and removed from the set at most once.
  • Space complexity: O(min(N, M))

3. Sliding Window with Last Seen Index Jump (Strictly O(N))

Intuition

Maintain a map or 128/256-size array lastSeen mapping each character to its most recent index. As right iterates from 0 to n - 1: if s[right] was seen previously, update left = max(left, lastSeen[s[right]] + 1). Then update lastSeen[s[right]] = right and maxLen = max(maxLen, right - left + 1).

When to apply: The standard gold standard solution for maximum efficiency and single pass execution.

Algorithm

  1. Initialize lastSeen array of size 128 or 256 filled with -1.
  2. Set left = 0, maxLen = 0.
  3. Loop right from 0 to s.length - 1:
  4. c = s[right]
  5. If lastSeen[c] != -1: left = max(left, lastSeen[c] + 1).
  6. lastSeen[c] = right
  7. maxLen = max(maxLen, right - left + 1)
  8. Return maxLen.

Dynamic Index Map Sliding Window Expansion

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a, b, c, b, b]
Current operationSTEP 1 OF 6
Observation: Read s[0] = 'a'
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
b
c
b
b
0
↑ L=0, R=0 ('a')
1
2
3
4
5
6
7
Variables at this step
L
0
R
0
char
a
lastSeen
{"a":0}
maxLen
1
Why this step matters

Observation: Read s[0] = 'a'. Character not in window.

Decision: Record lastSeen['a'] = 0. Window length 1 - 0 = 1. Update maxLen = 1.

Invariant: All characters in window [L, R] are strictly distinct.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int lengthOfLongestSubstring(std::string s) {
9 std::vector<int> lastSeen(256, -1);
10 int left = 0, maxLen = 0;
11 int n = s.size();
12
13 for (int right = 0; right < n; ++right) {
14 unsigned char c = s[right];
15 if (lastSeen[c] != -1) {
16 left = std::max(left, lastSeen[c] + 1);
17 }
18 lastSeen[c] = right;
19 maxLen = std::max(maxLen, right - left + 1);
20 }
21 return maxLen;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.lengthOfLongestSubstring("abcabcbb") << std::endl; // 3
28 std::cout << sol.lengthOfLongestSubstring("bbbbb") << std::endl; // 1
29 std::cout << sol.lengthOfLongestSubstring("pwwkew") << std::endl; // 3
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) strictly — Each character is evaluated exactly once in a single forward pass.
  • Space complexity: O(min(N, M)) where M <= 256 ASCII size

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All SubstringsO(N^3)O(min(N, M))Simple nested loops.Catastrophic timeout for N = 50,000.
2.Sliding Window with Hash Set (2N Steps)O(2N) = O(N)O(min(N, M))Very easy to understand; slides left boundary forward one step at a time.In the worst case, each character is visited twice (once by right, once by left).
3.Sliding Window with Last Seen Index Jump (Optimal)OptimalO(N) strictlyO(min(N, M)) (or 128/256 size array)Single pass; left pointer jumps directly to target position in O(1).Requires max(left, lastSeen + 1) boundary clamp.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting Math.max(left, lastSeen + 1) causing the left pointer to move backward when an old duplicate outside the current window is re-encountered (e.g. abba).

Pitfall 2:

Restricting character array to 26 letters when input contains symbols/digits.

Crucial Edge Cases to Validate:

  • Empty string s = "": Loop does not execute, returns 0.
  • All identical characters s = "bbbbb": left increments on every step, maxLen remains 1.
  • String with spaces and symbols (e.g., 'a b c a'): Using 256-size array or Map handles all ASCII characters seamlessly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the abba test case specifically to demonstrate why left = max(left, lastSeen[c] + 1) is critical.
  2. Highlight that using a fixed 256-size array achieves true O(1) extra space and single-pass O(N) execution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must we use left = max(left, lastSeen[c] + 1) instead of simply left = lastSeen[c] + 1?

Back to DSA Sheet