Longest Substring Without Repeating Characters is Day 10 of the Tekraze DSA series. It is where the two pointers from Days 6 to 9 grow into a new pattern called the sliding window. It is also one of the most asked string questions in interviews, and once it clicks, a whole family of problems becomes easy.
Also Read: Day 9, Container With Most Water shows the two pointer idea one last time before we turn it into a window.
What is the Longest Substring Without Repeating Characters problem?
You get a string s. Find the length of the longest substring that has no repeated characters. A substring must be continuous, so you cannot skip letters in the middle. This is the classic LeetCode problem 3.
text
Input: s = "abcabcbb" Output: 3 Why: "abc" is the longest part with all unique letters Input: s = "pwwkew" Output: 3 Why: "wke" works, but "pwke" is not continuous Input: s = "bbbbb" Output: 1
How should you think about the longest substring without repeating characters?
Picture a window sliding over the string. The right edge moves forward and pulls in one new character each step. While everything inside the window is unique, the window just grows.
The moment a character repeats, the window is broken. You push the left edge forward until the old copy of that character is outside. If you remember where you last saw each character, you can jump the left edge there in one step instead of crawling.
What does the brute force longest substring without repeating characters solution look like?
Start a substring at every index and extend it until you hit a repeat, keeping a set of characters seen so far.
python
def longest_brute(s):
best = 0
for i in range(len(s)):
seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
best = max(best, len(seen))
return best
Time is O(n²) in the worst case, since each start can scan far ahead. Space is O(k) for the set, where k is the number of distinct characters. This brute force approach works, but on a long string it repeats a lot of the same checks.
How do we get the optimal sliding window solution for the longest substring without repeating characters?
Keep a hash map from each character to the last index where you saw it, plus a left pointer for the start of the window. Walk right across the string. If the current character was seen inside the window, move left to one past that old index.
Then save the new index for the character and update the best length with right - left + 1.
Time is O(n) because right visits each character once and left only moves forward. Space is O(k) for the map, which is at most the alphabet size. If the jump from O(n²) to O(n) still feels abstract, our Big O helper post on time and space complexity explains it with simple charts.
Longest substring without repeating characters in Java
Java stores the last index in a HashMap keyed by char.
java
import java.util.HashMap;
import java.util.Map;
// Sliding window, jump left past the last copy of the repeated character
public class Solution {
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
Integer idx = lastSeen.get(ch);
if (idx != null && idx >= left) {
left = idx + 1;
}
lastSeen.put(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
String[] tests = {"abcabcbb", "bbbbb", "pwwkew", "", " ", "abba", "dvdf"};
int[] expected = {3, 1, 3, 0, 1, 2, 3};
for (int i = 0; i < tests.length; i++) {
int got = lengthOfLongestSubstring(tests[i]);
System.out.println((got == expected[i] ? "PASS " : "FAIL ") + "\"" + tests[i] + "\" " + got);
}
}
}
Longest substring without repeating characters in Python
Python keeps the same idea in a plain dict, so the code is the shortest of the three.
python
# Sliding window, jump left past the last copy of the repeated character
def length_of_longest_substring(s):
last_seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1
last_seen[ch] = right
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
tests = [("abcabcbb", 3), ("bbbbb", 1), ("pwwkew", 3), ("", 0),
(" ", 1), ("abba", 2), ("dvdf", 3)]
for s, want in tests:
got = length_of_longest_substring(s)
print("PASS" if got == want else "FAIL", repr(s), got)
Longest substring without repeating characters in Rust
Rust uses the standard library HashMap. Using usize for the indexes keeps the types simple, and left never goes below zero because it only moves forward.
rust
use std::collections::HashMap;
// Sliding window, jump left past the last copy of the repeated character
fn length_of_longest_substring(s: &str) -> usize {
let mut last_seen: HashMap<char, usize> = HashMap::new();
let (mut left, mut best) = (0usize, 0usize);
for (right, ch) in s.chars().enumerate() {
if let Some(&idx) = last_seen.get(&ch) {
if idx >= left {
left = idx + 1;
}
}
last_seen.insert(ch, right);
best = best.max(right - left + 1);
}
best
}
fn main() {
let tests = [("abcabcbb", 3), ("bbbbb", 1), ("pwwkew", 3), ("", 0),
(" ", 1), ("abba", 2), ("dvdf", 3)];
for (s, want) in tests {
let got = length_of_longest_substring(s);
println!("{} {:?} {}", if got == want { "PASS" } else { "FAIL" }, s, got);
}
}
Test results
All three programs for the longest substring without repeating characters ran on the same seven tests: “abcabcbb”, “bbbbb”, “pwwkew”, an empty string, a single space, “abba” and “dvdf”. Every test passed in Java, Python and Rust.
The “abba” case is the sneaky one. It checks that left never moves backwards.
What are the 6 best tips for the longest substring without repeating characters?
- Spot the pattern. When a question like the longest substring without repeating characters says longest or shortest continuous substring or subarray with some rule, think sliding window straight away.
- Store indexes, not counts. Saving the last index of each character lets the left edge jump in one step instead of shrinking one by one.
- Never move left backwards. Only jump when the old index is inside the window, or use
max(left, last + 1). - Use an array for small alphabets. If the input is plain ASCII, an int array of size 128 is faster than a hash map and just as simple.
- Test the tricky cases. Empty string, all same letters, spaces, and patterns like “abba” and “dvdf” catch most bugs.
- Explain it in one sentence in interviews. Describe the brute force, then say the window only moves forward, so the total work is linear. That shows you understand why it is fast.
What are the common mistakes in the longest substring without repeating characters problem?
- Moving
leftback to an older index when the repeated character was already outside the window. - Mixing up substring and subsequence, and counting letters that are not next to each other.
- Computing the length as
right - leftinstead ofright - left + 1. - Resetting the whole set on a repeat and restarting from scratch, which brings back O(n²).
- Forgetting the empty string and returning something other than 0.
Where is the longest substring without repeating characters pattern used in the real world?
Sliding windows are everywhere in real systems. Rate limiters count requests in the last few seconds with a moving window. Network tools use windows to track packets in flight.
Analytics dashboards show rolling averages over the last hour or week. Log and fraud checks scan streams for the longest run of unique sessions or events without a repeat. Whenever you look at a moving, continuous chunk of data, this is the pattern behind it.
Which earlier posts in the series should you read?
Start with Day 1, Two Sum, where we first used a hash map to remember what we had seen. Day 2, Best Time to Buy and Sell Stock shows the one pass idea of tracking the best answer so far. Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams build the hashing toolkit we lean on today.
The two pointer idea starts in Day 6, Valid Palindrome. It continues in Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water. Today, the longest substring without repeating characters turns those pointers into a window.
Conclusion
Longest Substring Without Repeating Characters comes down to one move: remember the last index of each character, and never let left go backwards. Solve it once in your favorite language, then try the “abba” test by hand. Next up, we keep going with more sliding window problems.
Frequently asked questions
What is the time complexity of Longest Substring Without Repeating Characters?
The sliding window solution runs in O(n) time with O(k) space, where k is the number of distinct characters. The brute force version takes O(n²) time.
Why is the longest substring without repeating characters a sliding window problem?
You keep a continuous range of the string between two pointers. The right pointer grows the window and the left pointer shrinks it when a repeat appears, so the window slides across the string.
What is the difference between a substring and a subsequence here?
A substring must be continuous. In “pwwkew” the answer is “wke” with length 3, while “pwke” is a subsequence and does not count.
Can I use an array instead of a hash map for the longest substring without repeating characters?
Yes. If the input only has ASCII characters, an int array of size 128 storing last positions works the same way and is usually faster.
Why does the abba test case matter for the longest substring without repeating characters?
When the second “a” arrives, its old index is already outside the window. If you move left back to that old index, the answer becomes wrong, so left must only move forward.
