Algorithm-Day08-Longest-Substring-Without-Repeating-Characters-lc-3

🧩 Problem Description

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

💡 Brute Force (Too Slow)

Try all substrings and check if characters are unique.

• Time: O(n³)
• Space: O(k) for checking duplicates

✅ Correct but ❌ inefficient.

---

💡 Optimized Approach: Sliding Window + HashMap

We use a sliding window with two pointers:

• Expand right to include new characters
• If a duplicate is found, move left to skip past the previous occurrence
• Use a HashMap to store the last index of each character

🔢 Java Code

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

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

            if (map.containsKey(ch)) {
                // Move left pointer past the previous occurrence of ch
                left = Math.max(left, map.get(ch) + 1);
            }

            map.put(ch, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each character is visited at most twice.
• Space Complexity: O(k)
  Where k is the number of unique characters (e.g. 26 for lowercase letters, 128 for ASCII)

---

✍️ Summary

• Sliding window is ideal for “longest substring” problems.
• Key trick: update left pointer only when needed, and never move it backward.
• Using a HashMap allows constant-time character index tracking.

This is one of the most popular sliding window problems — understanding this unlocks many similar challenges like Longest Subarray with Sum ≤ k, or Minimum Window Substring.