Longest Substring Without Repeating Characters

Problem Statement

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

A substring is a contiguous sequence of characters within the string. You must return the length (integer), not the substring itself.

What to notice first

• You need to find a contiguous sequence, not just any selection of characters.
• The answer is the length, not the substring.
• The sliding window pattern is the gold standard here: move the right pointer forward and shrink from the left when a duplicate appears.
• A hash map or set to track which characters are in the current window is essential.

Examples

Input	Output	Explanation
"abcabcbb"	3	The longest substring is "abc", which has length 3.
"bbbbb"	1	The longest substring is "b", which has length 1.
"pwwkew"	3	The longest substring is "wke" or "kew", which has length 3.
""	0	Empty string has no substring.
"au"	2	The longest substring is "au", which has length 2.

Constraints

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

Real-World Applications

Where this pattern appears

• Password validation — ensure a user’s password has a minimum number of consecutive unique characters without repetition.
• Data deduplication — find the longest run of unique identifiers in a stream of log entries.
• Session token parsing — extract the longest valid session segment where no character repeats.
• DNA sequence analysis — identify the longest stretch of consecutive unique bases (A, T, G, C) in genomic data.
• Token/identifier validation — verify that API rate limits or access tokens contain a unique substring of sufficient length.

Complexity Comparison

Approach	Time	Space	Returns	Best When
Brute Force	O(n³)	O(min(n, m))	Length	String is tiny, practicing the concept, or interviewer explicitly requests it
Sliding Window	O(n)	O(min(n, m))*	Length	General case — fast, clean, and efficient

* Space is proportional to the character set size, not string length. For English letters only, this is O(26) = O(1).

Which approach should you learn first?

• Pick Sliding Window if you want the best all-around interview answer.
• Pick Brute Force if you are still learning how to think about substrings.
• Every interviewer expects the sliding window solution for this problem.

Best For Speed

Sliding Window

O(n) time · O(min(n, m)) space

Learning Tool

Brute Force

O(n³) time · O(min(n, m)) space

Approach 1: Sliding Window with Hash Map (Recommended)

★ Recommended

Use two pointers (left and right) to maintain a window. Expand the window by moving right forward. When a character is seen that already exists in the current window, shrink the window from the left until the duplicate is removed.

The key insight is that each character is visited at most twice (once by right, once by left), making this a single linear pass through the string.

⏱ Time O(n) Each character visited once per pointer 💾 Space O(min(n, m)) Character set (max 26 letters or full Unicode)

Step-by-step Example

Input: s = "abcabcbb"

Step	left	right	char	window	seen	max_length	Action
1	0	0	’a’	"a"	{a:0}	1	Add ‘a’, expand
2	0	1	’b’	"ab"	{a:0, b:1}	2	Add ‘b’, expand
3	0	2	’c’	"abc"	{a:0, b:1, c:2}	3	Add ‘c’, expand
4	0	3	’a’	"bca"	{b:1, c:2, a:3}	3	’a’ seen at 0, move left to 1, update ‘a’ to 3
5	1	4	’b’	"cab"	{c:2, a:3, b:4}	3	’b’ seen at 1, move left to 2, update ‘b’ to 4
6	2	5	’c’	"abc"	{a:3, b:4, c:5}	3	’c’ seen at 2, move left to 3, update ‘c’ to 5
7	3	6	’b’	"ab"	{a:3, b:6, c:5}	3	’b’ seen at 4, move left to 5, update ‘b’ to 6
8	5	7	’b’	"b"	{b:7, c:5}	3	’b’ seen at 6, move left to 7, update ‘b’ to 7

Animated walkthrough

How the sliding window finds the longest substring

Use Next or Autoplay to watch the window expand and contract as characters are processed. Notice how the left pointer jumps when a duplicate is found.

Back Autoplay Next Reset

Step 1 of 8

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function longestSubstringWithoutRepeatingCharactersSlidingWindow(s):
    charIndex = {}
    maxLength = 0
    left = 0

    for right from 0 to len(s) - 1:
        if s[right] in charIndex and charIndex[s[right]] >= left:
            left = charIndex[s[right]] + 1
        charIndex[s[right]] = right
        maxLength = max(maxLength, right - left + 1)

    return maxLength

Solution Code

Python

longest_substring_without_repeating_characters_sliding_window.py

def longest_substring_without_repeating_characters_sliding_window(s: str) -> int:
    char_index = {}
    max_length = 0
    left = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length

print(longest_substring_without_repeating_characters_sliding_window("abcabcbb"))  # 3

C++

longest_substring_without_repeating_characters_sliding_window.cpp

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>

int longest_substring_without_repeating_characters_sliding_window(std::string s) {
    std::unordered_map<char, int> char_index;
    int max_length = 0;
    int left = 0;

    for (int right = 0; right < (int)s.length(); right++) {
        if (char_index.count(s[right]) && char_index[s[right]] >= left) {
            left = char_index[s[right]] + 1;
        }
        char_index[s[right]] = right;
        max_length = std::max(max_length, right - left + 1);
    }

    return max_length;
}

int main() {
    std::string s = "abcabcbb";
    std::cout << longest_substring_without_repeating_characters_sliding_window(s) << std::endl;
    return 0;
}

Java

longest_substring_without_repeating_characters_sliding_window.java

import java.util.HashMap;

public class Main {
    public static int longestSubstringWithoutRepeatingCharactersSlidingWindow(String s) {
        HashMap<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
                left = charIndex.get(c) + 1;
            }
            charIndex.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(longestSubstringWithoutRepeatingCharactersSlidingWindow(s));
    }
}

JavaScript

longest_substring_without_repeating_characters_sliding_window.js

function longestSubstringWithoutRepeatingCharactersSlidingWindow(s) {
    const charIndex = {};
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        if (s[right] in charIndex && charIndex[s[right]] >= left) {
            left = charIndex[s[right]] + 1;
        }
        charIndex[s[right]] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

const s = "abcabcbb";
const result = longestSubstringWithoutRepeatingCharactersSlidingWindow(s);
console.log(result);

Rust

longest_substring_without_repeating_characters_sliding_window.rs

use std::collections::HashMap;

fn longest_substring_without_repeating_characters_sliding_window(s: &str) -> usize {
    let mut char_index: HashMap<char, usize> = HashMap::new();
    let mut max_length = 0;
    let mut left = 0;

    for (right, c) in s.chars().enumerate() {
        if let Some(&prev_index) = char_index.get(&c) {
            if prev_index >= left {
                left = prev_index + 1;
            }
        }
        char_index.insert(c, right);
        max_length = max_length.max(right - left + 1);
    }

    max_length
}

fn main() {
    let s = "abcabcbb";
    let result = longest_substring_without_repeating_characters_sliding_window(s);
    println!("{}", result);
}

Go

longest_substring_without_repeating_characters_sliding_window.go

package main

import "fmt"

func longestSubstringWithoutRepeatingCharactersSlidingWindow(s string) int {
  charIndex := make(map[rune]int)
  maxLength := 0
  left := 0

  for right, c := range s {
    if prevIndex, ok := charIndex[c]; ok && prevIndex >= left {
      left = prevIndex + 1
    }
    charIndex[c] = right
    if right-left+1 > maxLength {
      maxLength = right - left + 1
    }
  }

  return maxLength
}

func main() {
  s := "abcabcbb"
  result := longestSubstringWithoutRepeatingCharactersSlidingWindow(s)
  fmt.Println(result)
}

Approach 2: Brute Force

✓ Simple

Check every possible substring and find the longest one without repeating characters.

For each starting position i, extend to position j and check if all characters from i to j are unique. Keep track of the maximum length found.

This approach is slow but instructive: it explicitly shows what a “valid substring” is.

⏱ Time O(n³) Three nested loops: i, j, and checking duplicates 💾 Space O(min(n, m)) Set for characters in current window

Step-by-step Example

Input: s = "abcabcbb"

i	j	substring	has duplicate?	action	max_length
0	0	”a”	No	Add to set, update max	1
0	1	”ab”	No	Add ‘b’, update max	2
0	2	”abc”	No	Add ‘c’, update max	3
0	3	”abca”	Yes (‘a’)	Break inner loop	3
1	1	”b”	No	Start new substring	3
1	2	”bc”	No	Add ‘c’, max stays 3	3
1	3	”bca”	No	Add ‘a’, max stays 3	3
1	4	”bcab”	Yes (‘b’)	Break	3

Pseudocode

function longestSubstringWithoutRepeatingCharactersBruteForce(s):
    maxLength = 0

    for i from 0 to len(s) - 1:
        charSet = {}
        for j from i to len(s) - 1:
            if s[j] in charSet:
                break
            charSet.add(s[j])
            maxLength = max(maxLength, j - i + 1)

    return maxLength

Solution Code

Python

longest_substring_without_repeating_characters_brute_force.py

def longest_substring_without_repeating_characters_brute_force(s: str) -> int:
    max_length = 0

    for i in range(len(s)):
        char_set = set()
        for j in range(i, len(s)):
            if s[j] in char_set:
                break
            char_set.add(s[j])
            max_length = max(max_length, j - i + 1)

    return max_length

print(longest_substring_without_repeating_characters_brute_force("abcabcbb"))  # 3

C++

longest_substring_without_repeating_characters_brute_force.cpp

#include <iostream>
#include <unordered_set>
#include <string>
#include <algorithm>

int longest_substring_without_repeating_characters_brute_force(std::string s) {
    int max_length = 0;

    for (int i = 0; i < (int)s.length(); i++) {
        std::unordered_set<char> char_set;
        for (int j = i; j < (int)s.length(); j++) {
            if (char_set.count(s[j])) {
                break;
            }
            char_set.insert(s[j]);
            max_length = std::max(max_length, j - i + 1);
        }
    }

    return max_length;
}

int main() {
    std::string s = "abcabcbb";
    std::cout << longest_substring_without_repeating_characters_brute_force(s) << std::endl;
    return 0;
}

Java

longest_substring_without_repeating_characters_brute_force.java

import java.util.HashSet;

public class Main {
    public static int longestSubstringWithoutRepeatingCharactersBruteForce(String s) {
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            HashSet<Character> charSet = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                if (charSet.contains(s.charAt(j))) {
                    break;
                }
                charSet.add(s.charAt(j));
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(longestSubstringWithoutRepeatingCharactersBruteForce(s));
    }
}

JavaScript

longest_substring_without_repeating_characters_brute_force.js

function longestSubstringWithoutRepeatingCharactersBruteForce(s) {
    let maxLength = 0;

    for (let i = 0; i < s.length; i++) {
        const charSet = new Set();
        for (let j = i; j < s.length; j++) {
            if (charSet.has(s[j])) {
                break;
            }
            charSet.add(s[j]);
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }

    return maxLength;
}

const s = "abcabcbb";
const result = longestSubstringWithoutRepeatingCharactersBruteForce(s);
console.log(result);

Rust

longest_substring_without_repeating_characters_brute_force.rs

use std::collections::HashSet;

fn longest_substring_without_repeating_characters_brute_force(s: &str) -> usize {
    let mut max_length = 0;

    for i in 0..s.len() {
        let mut char_set: HashSet<char> = HashSet::new();
        for (j, c) in s.chars().enumerate().skip(i) {
            if char_set.contains(&c) {
                break;
            }
            char_set.insert(c);
            max_length = max_length.max(j - i + 1);
        }
    }

    max_length
}

fn main() {
    let s = "abcabcbb";
    let result = longest_substring_without_repeating_characters_brute_force(s);
    println!("{}", result);
}

Go

longest_substring_without_repeating_characters_brute_force.go

package main

import "fmt"

func longestSubstringWithoutRepeatingCharactersBruteForce(s string) int {
  maxLength := 0

  for i := 0; i < len(s); i++ {
    charSet := make(map[rune]bool)
    for j, c := range s[i:] {
      if charSet[c] {
        break
      }
      charSet[c] = true
      if i+j+1 > maxLength {
        maxLength = i + j + 1
      }
    }
  }

  return maxLength
}

func main() {
  s := "abcabcbb"
  result := longestSubstringWithoutRepeatingCharactersBruteForce(s)
  fmt.Println(result)
}

Common mistakes

Watch for these pitfalls

• Returning the substring instead of the length. The problem asks for the length as an integer, not the substring.
• Forgetting to move the left pointer when a duplicate is found. The window must shrink to exclude the duplicate.
• Off-by-one errors with window size. The window size is right - left + 1, not right - left.
• Not updating the character’s position in the hash map. Always update after moving left, or the next check will reference a stale index.
• Using a set instead of tracking indices. A set works but doesn’t tell you where the duplicate is, forcing extra work to shrink the window correctly.
• Assuming ASCII characters only. Unicode characters, digits, and symbols are valid and should be handled the same way.

Approach 3: Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

longest_substring_without_repeating_characters_optimized.py

"""
Solution for Longest Substring Without Repeating Characters
"""

def solve():
    """Implementation for approach 3 of Longest Substring Without Repeating Characters"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

longest_substring_without_repeating_characters_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Longest Substring Without Repeating Characters
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

LongestSubstringWithoutRepeatingCharactersOptimized.java

/**
 * Solution for Longest Substring Without Repeating Characters
 * Approach 3
 */
public class LongestSubstringWithoutRepeatingCharactersOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

longest_substring_without_repeating_characters_optimized.js

/**
 * Solution for Longest Substring Without Repeating Characters
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

longest_substring_without_repeating_characters_optimized.rs

/// Solution for Longest Substring Without Repeating Characters
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

longest_substring_without_repeating_characters_optimized.go

package main

import "fmt"

// Solution for Longest Substring Without Repeating Characters
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Add Two Numbers ↗ Medium #2
• Minimum Window Substring ↗ Hard #76
• Longest Substring with At Most Two Distinct Characters ↗ Medium #159
• Permutation in String ↗ Medium #567

Interview Tips

Key trade-offs to discuss

• Why sliding window over brute force? A dramatic drop from O(n³) to O(n). The sliding window is the standard for any “longest/shortest substring” problem.
• How do you know when to use sliding window? Look for the key pattern: you want a contiguous element (substring, subarray) that satisfies a property. Sliding window is almost always the answer.
• Edge cases to mention: empty string (answer is 0), single character (answer is 1), all unique characters (answer is the string length), all duplicates like “aaaa” (answer is 1).
• Follow-up questions you should be ready for:
  • Return the actual substring, not just the length → track start and end indices.
  • Handle multiple character sets (Unicode) → the approach is identical; just ensure your hash map supports any character type.
  • Find all substrings of the maximum length → collect them as you track the max.
• Common interviewer follow-up: “Can you do this with O(1) space if the string contains only lowercase English letters?” Answer: Yes, use a 26-element array instead of a hash map.

← Previous
#1 Two Sum Next
#9 Palindrome Number →