Problem

Find the length of the longest substring without repeating characters. A substring is a continuous part of a string; characters cannot be skipped.

View the problem on LeetCode.

Examples

Input	Answer	One longest substring
"abcabcbb"	3	"abc"
"bbbbb"	1	"b"
"pwwkew"	3	"wke"
""	0	Empty string

In "pwwkew", "pwke" is not a substring because it skips a character.

Constraints

• 0 <= s.length() <= 10^5
• The string contains English letters, digits, symbols, and spaces.

Solution

Approach - Sliding window with last-seen indices

This follows Pattern 2: longest valid window.

Keep a window from l to r and a map storing each character's latest index.

For each character at r:

1. Look up its previous index.
2. If that index is inside the window (prevIndex >= l), move l to prevIndex + 1, just past the duplicate.
3. Store the current index and update the maximum using r - l + 1.

After moving l, the window has no duplicates. Jumping just past the previous occurrence removes the duplicate while keeping the longest valid window ending at r.

Why must we check prevIndex >= l?

A character's previous occurrence may already be outside the window. Never move l backward.

For s = "abba" (indices start at 0):

r	Character	Action	Valid window	Best length
0	a	First occurrence	"a"	1
1	b	First occurrence	"ab"	2
2	b	Previous index 1 is inside; move l to 2	"b"	2
3	a	Previous index 0 is outside; keep l = 2	"ba"	2

At the final a, moving l backward to 1 would create "bba", which contains a duplicate.

Java solution

My solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int r = 0;
        int n = s.length();
        int maxLength = 0;

        Map<Character, Integer> lastSeen = new HashMap<>();

        for (r = 0; r < n; r++) {
            char chr = s.charAt(r);

            if (lastSeen.containsKey(chr)) {
                int prevIndex = lastSeen.get(chr);
                if (l <= prevIndex) {
                    l = prevIndex;
                    l += 1;
                }
            }

            lastSeen.put(chr, r);
            maxLength = Math.max(maxLength, r - l + 1);
        }

        return maxLength;
    }
}

Cleaner version

The same logic, with one map lookup and a single assignment to move l.

import java.util.HashMap;
import java.util.Map;

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

        for (int r = 0; r < s.length(); r++) {
            char chr = s.charAt(r);
            Integer prevIndex = lastSeen.get(chr);

            // Skip the duplicate only if it is inside the window.
            if (prevIndex != null && prevIndex >= l) {
                l = prevIndex + 1;
            }

            lastSeen.put(chr, r);
            maxLength = Math.max(maxLength, r - l + 1);
        }

        return maxLength;
    }
}

Complexity

• Time: O(n) expected — visit each character once, with expected O(1) map operations.
• Extra space: O(min(n, A)) — one entry per distinct character, where A is the character-set size.