Welcome to Day 2 of your coding interview journey.

Yesterday we covered HashMaps, and today we’ll combine that knowledge with a powerful technique used in many top interview problems:

👉 Sliding Window

This pattern helps you turn slow O(n²) solutions into efficient O(n) ones.

---

🧠 What is the Sliding Window Technique?

The Sliding Window is used to process subarrays or substrings efficiently by maintaining a “window” that moves through the data.

Instead of recalculating everything repeatedly, you:

1. Expand the window ➡️
2. Shrink the window ⬅️
3. Keep track of useful data (often using a HashMap or Set)

---

🔑 When Should You Use Sliding Window?

Think about this pattern when you see:

• Substrings / subarrays
• “Longest”, “Shortest”, “Maximum”, “Minimum”
• Contiguous sequences
• Conditions involving uniqueness or counts

---

💡 Interview Pattern – Longest Substring Without Repeating Characters

This is a must-know problem. It appears in interviews at companies like Google, Amazon, and Meta.

---

🧩 Problem

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

---

❌ Brute Force Approach

• Generate all substrings
• Check each one

👉 Time Complexity: O(n²) (too slow for interviews)

---

✅ Optimal Approach – Sliding Window + Set

We use:

• A set to track characters in the window
• Two pointers (left and right)

---

🛠️ Solution in Python

def longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # If duplicate, shrink window
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

---

✅ Example

s = "abcabcbb"
print(longest_substring(s))

Output:

3  # "abc"

---

🎯 Step-by-Step Intuition

For "abcabcbb":

• Start expanding: "a" → "ab" → "abc" ✅
• Hit duplicate "a" ❌
• Move left pointer until valid again
• Continue…

👉 The window always contains unique characters

---

⚡ Complexity Analysis

• Time Complexity: O(n)
  Each character is visited at most twice
• Space Complexity: O(min(n, charset))

---

🔥 Optimized Version (Using HashMap)

We can skip unnecessary steps by jumping the left pointer:

def longest_substring_optimized(s):
    char_map = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1

        char_map[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

👉 This version is cleaner and often preferred in interviews.

---

⚠️ Common Mistakes

• ❌ Forgetting to shrink the window properly
• ❌ Not updating left correctly
• ❌ Using brute force instead of optimizing
• ❌ Confusing substring vs subsequence

---

🧪 Practice Problems

To master Sliding Window, try:

1. Longest repeating character replacement
2. Minimum window substring
3. Permutation in string
4. Maximum sum subarray of size K
5. Find all anagrams in a string

---

🎯 Key Takeaways

• Sliding Window reduces complexity from O(n²) → O(n)
• Works best with:
  • Contiguous data
  • Dynamic conditions
• Often combined with:
  • HashMaps
  • Sets

---

🚀 Your Challenge (Day 2)

Solve this:

Given a string, find the length of the longest substring with at most 2 distinct characters.

---

📌 Final Thoughts

Sliding Window is a game-changer for coding interviews.

If you master this pattern, you’ll unlock a huge category of problems that many candidates struggle with.

Tomorrow, we’ll continue leveling up. 💪