Longest Substring Without Repeating Characters DSA Solution - Study Chapter | QuizMaker

Longest Substring Without Repeating Characters explained with brute force, optimized sliding window, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 2: Strings

Learning Outcome

After this lesson, you should be able to maintain a duplicate-free window and move the left boundary only when a repeated character breaks the window.

Problem Statement

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

Input	Output	Why
`"abcabcbb"`	`3`	The longest duplicate-free substring is `"abc"`.
`"bbbbb"`	`1`	Only one repeated character can be kept at a time.

Brute Force Approach

Start from every index and extend until a duplicate appears. Track the maximum valid length.

This repeats scans from many start positions, so the worst-case time is O(n^2).

Optimized Approach

Use a sliding window [left, right]. Store the last index where each character appeared. When the current character was seen inside the current window, move left just after that old index.

Never move left backward. That one rule keeps the window valid and linear.

Exact Pseudocode

lastSeen = empty map
left = 0
best = 0
for right from 0 to length(s) - 1:
  char = s[right]
  if char exists in lastSeen and lastSeen[char] >= left:
    left = lastSeen[char] + 1
  lastSeen[char] = right
  best = max(best, right - left + 1)
return best

Reference Code

class Solution:
    def lengthOfLongestSubstring(self, s):
        last_seen = {}
        left = 0
        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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> lastSeen;
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.size(); right++) {
            char ch = s[right];
            if (lastSeen.count(ch) && lastSeen[ch] >= left) {
                left = lastSeen[ch] + 1;
            }
            lastSeen[ch] = right;
            best = max(best, right - left + 1);
        }

        return best;
    }
};

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0;
        int best = 0;

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

        return best;
    }
}

Sample Dry Run

right	char	left	window	best
0	a	0	`a`	1
1	b	0	`ab`	2
2	c	0	`abc`	3
3	a	1	`bca`	3
4	b	2	`cab`	3

Complexity

Measure	Value	Reason
Time	O(n)	Each index is processed once.
Space	O(k)	The map stores last positions for distinct characters.

Edge Cases

Empty string returns 0.
All characters same returns 1.
Repeated character appears before the current window and should not move left backward.

Interview Checklist

Define the window invariant: no duplicate characters inside it.
Use last seen index to jump left.
Update answer after fixing the window.

FAQs

Why use last seen index instead of a set?

A set works too, but last seen index lets you jump the left boundary directly.

Why use max(left, lastSeen + 1) logic?

It prevents moving left backward when a duplicate is outside the current window.

What is the core pattern?

Sliding window with last-seen positions.