Longest substring without repeating characters
Find the length of the longest contiguous substring whose characters are all distinct.
Course progress
Problem 40 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
text = "abcabcbb"
Expected output
3
What is happening?
The opening substring abc contains three distinct characters. Every longer window repeats at least one character, so the maximum length is 3.
Solution strategy
Build the right mental model
Maintain a sliding window start and each character's latest index. When a repeated character is inside the window, move the start just past its previous position.
Core concepts
sliding window · dictionary
Complexity
Time O(n), space O(k), where k is the character set size.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for longest-substring-without-repeats
using System;
using System.Collections.Generic;
class Program
{
static int LongestDistinctSubstring(string text)
{
var lastSeen = new Dictionary<char, int>();
int start = 0;
int best = 0;
for (int end = 0; end < text.Length; end++)
{
int previous;
if (lastSeen.TryGetValue(text[end], out previous) && previous >= start)
start = previous + 1;
lastSeen[text[end]] = end;
best = Math.Max(best, end - start + 1);
}
return best;
}
static void Main()
{
Console.WriteLine(LongestDistinctSubstring("abcabcbb"));
}
}Knowledge check
Questions students often ask
What is the main idea behind longest substring without repeating characters?
Maintain a sliding window start and each character's latest index. When a repeated character is inside the window, move the start just past its previous position.
What is the time and space complexity of this solution?
Time O(n), space O(k), where k is the character set size.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.