Problem Summary

You are given a string s.
Your task is to find the length of the longest substring that contains no repeated characters.

A substring means a continuous block of characters.

Examples
Input: "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc".

Input: "bbbbb"
Output: 1
Explanation: The longest substring without repeating characters is "b".

Input: "pwwkew"
Output: 3
Explanation: The longest substring is "wke".

Constraints
Length of the string can be up to 100,000.
Characters are standard ASCII.

---

Approach in Simple English

The goal is to find the longest substring that has all unique characters.

Instead of checking every possible substring (which is very slow), we use a much faster technique called the sliding window.

How sliding window helps
Imagine two pointers, left and right, that mark the current window (current substring).
We expand the window by moving right forward, but if we see a repeated character, we shrink the window from the left until the duplicate goes away.

To detect duplicates efficiently, we can use a map (or an array) to store the last seen index of each character.

Step-by-step logic

1. Move right pointer through the string, one character at a time.
2. If the character at right was seen before and its index is inside the current window, move the left pointer to one position ahead of that previous index.
3. Update the last seen index for the character.
4. Calculate the current window length:
   window size = right – left + 1
5. Track the maximum window size found so far.

This guarantees an O(n) solution because each pointer only moves forward.

---

Java Code (Optimal Sliding Window)

class Solution {
    public int lengthOfLongestSubstring(String s) {

        int left = 0;
        int maxLen = 0;

        // To store the last seen position of each character
        int[] lastSeen = new int[128];
        // Initialize with -1 (means not seen)
        for (int i = 0; i < 128; i++) {
            lastSeen[i] = -1;
        }

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // If we have seen this character and it is inside the window
            if (lastSeen >= left) {
                left = lastSeen + 1;
            }

            // Update last seen index
            lastSeen = right;

            // Update max length
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

---

Dry Run (Step-by-Step Explanation)

Dry run input

s = "abcabcbb"

Initial

left = 0
maxLen = 0
lastSeen[] = all -1

Step 1

right = 0, char = 'a'
lastSeen['a'] = -1 (not seen)
Window = [0,0] → "a"
maxLen = 1
Update lastSeen['a'] = 0

Step 2

right = 1, char = 'b'
lastSeen['b'] = -1
Window = [0,1] → "ab"
maxLen = 2
Update lastSeen['b'] = 1

Step 3

right = 2, char = 'c'
lastSeen['c'] = -1
Window = [0,2] → "abc"
maxLen = 3
Update lastSeen['c'] = 2

Step 4

right = 3, char = 'a'
lastSeen['a'] = 0, and 0 >= left(0)

So, shift left:
left = lastSeen['a'] + 1 = 0 + 1 = 1

Window = [1,3] → "bca"
maxLen still = 3
Update lastSeen['a'] = 3

Step 5

right = 4, char = 'b'
lastSeen['b'] = 1, and 1 >= left(1)

left = 1 + 1 = 2

Window = [2,4] → "cab"
maxLen = 3
Update lastSeen['b'] = 4

Step 6

right = 5, char = 'c'
lastSeen['c'] = 2, and 2 >= left(2)

left = 2 + 1 = 3

Window = [3,5] → "abc"
maxLen = 3
Update lastSeen['c'] = 5

Step 7

right = 6, char = 'b'
lastSeen['b'] = 4, and 4 >= left(3)

left = 4 + 1 = 5

Window = [5,6]
maxLen = 3
Update lastSeen['b'] = 6

Step 8

right = 7, char = 'b'
lastSeen['b'] = 6, and 6 >= left(5)

left = 6 + 1 = 7

Window = [7,7]
maxLen remains = 3
Update lastSeen['b'] = 7

Final result

maxLen = 3

---

Key Takeaways

The sliding window technique is the most efficient way to solve substring problems.
Tracking last-seen positions lets us jump the left pointer correctly.
Both pointers move only forward, ensuring O(n) time.
This method avoids checking each substring explicitly, which would be too slow.