🚀 Finding the Length of the Longest Substring Without Repeating Characters

When preparing for interviews or working with string algorithms, one classic problem is:

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

Example:

• Input: "abcabcbb"

• Output: 3 (because "abc" is the longest substring without repeating chars)

---

🧩 Problem Intuition

We want the longest contiguous substring where no character repeats.
Naively, we could try every substring (O(n²)) and check uniqueness, but that’s too slow for larger inputs.

Instead, we use a sliding window:

• Expand the right boundary to include characters.

• If a duplicate appears, shrink the left boundary until the window is valid again.

• Track the maximum length as we go.

---

🛠️ Sliding Window + Hashing Approach

Core Ideas:

1. Maintain two pointers: l (left) and r (right).

2. Keep a map of last-seen indices of each character.

3. For each character at r:

   • If it’s already in the current window (map[ch] >= l), move l to map[ch] + 1.

   • Update the last-seen index of ch.

   • Update the max length.

This ensures each character is processed at most twice (once when r expands, once when l moves), giving us O(n) time.

---

💻 Java Implementation

import java.util.Arrays;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0;
        int[] map = new int[256]; // supports ASCII
        Arrays.fill(map, -1);

        int maxLen = 0;
        while (r < s.length()) {
            char ch = s.charAt(r);

            // if char seen in current window, move left pointer
            if (map[ch] >= l) {
                l = map[ch] + 1;
            }

            // update window
            map[ch] = r;
            maxLen = Math.max(maxLen, r - l + 1);

            r++;
        }
        return maxLen;
    }
}

---

📊 Complexity Analysis

• Time Complexity: O(n) → each character visited at most twice.

• Space Complexity: O(1) → fixed-size array (256) for ASCII.
  For Unicode, switch to HashMap<Character,Integer>.

---

🔑 Key Takeaways

• Sliding window problems often involve two pointers and a hash structure.

• Always update your left pointer only when duplicates fall inside the current window.

• This problem demonstrates the balance between correctness and efficiency — no need to brute force!

---

✅ Next step: try extending this logic to variations like:

• Longest substring with at most k distinct characters

• Longest substring where characters can repeat up to m times