ABC TO XYZ OF AI

📘 Topic 2: Sliding Window (20 Problems)

Each problem is solved using the enhanced template with pseudocode, dry run, code, and explanations.

🔹 1. Maximum Sum Subarray of Size K

🧠 Problem Statement: Find the maximum sum of any contiguous subarray of size k in the given array.

Input/Output:

• Input: arr = [2, 1, 5, 1, 3, 2], k = 3
• Output: 9

✏️ Pseudocode:

1. Initialize max_sum and window_sum = 0
2. Use a sliding window of size k
3. Slide the window and keep updating max_sum

🧰 Tools Chosen:

• Sliding Window technique
• Window sum tracking

🧪 Dry Run:

• Start with sum of first 3: 2+1+5=8 → slide → 1+5+1=7 → 5+1+3=9 (max)

💻 Code:

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))

✅ Output: 9

🧠 Enhancements:

• Complexity: O(n), Space: O(1)
• Add edge case checks (if len < k)

🔹 2. First Negative Number in Every Window of Size K

🧠 Problem Statement: Given an array, print the first negative number in every window of size k.

Input/Output:

• Input: arr = [12, -1, -7, 8, -15, 30, 16, 28], k = 3
• Output: [-1, -1, -7, -15, -15, 0]

✏️ Pseudocode:

1. Use a deque to track negative numbers
2. For every window:
   - Append new negative
   - Pop out-of-window elements
   - Append result

🧰 Tools Chosen:

• Deque for O(1) access
• Sliding Window

🧪 Dry Run:

• Window [12, -1, -7] → first negative = -1 → [-1, -1, -7…]

💻 Code:

from collections import deque

def first_negative_k(arr, k):
    q, res = deque(), []
    for i in range(len(arr)):
        if arr[i] < 0:
            q.append(i)
        if i >= k-1:
            while q and q[0] < i-k+1:
                q.popleft()
            res.append(arr[q[0]] if q else 0)
    return res

print(first_negative_k([12, -1, -7, 8, -15, 30, 16, 28], 3))

✅ Output: [-1, -1, -7, -15, -15, 0]

🧠 Enhancements:

• Use list comprehensions or numpy for speed if needed

📘 Topic 2: Sliding Window (20 Problems with Template-Based Solutions)

Problem 3: Count Occurrences of Anagrams

🧠 0. Understand the Problem

• Problem Statement: Count how many times an anagram of p appears in string s.
• Input/Output:
  • Input: s = "cbaebabacd", p = "abc"
  • Output: 2 (anagrams found at indices 0 and 6)
• Constraints:
  • s and p are lowercase
  • Length of s ≥ length of p
• Keywords: Anagram, Frequency Map, Sliding Window

✏️ 1. Write Pseudocode / Flow

Create a frequency map for p
Use a sliding window of size len(p) on s
At each step:
    update the frequency of current window
    compare window frequency with pattern frequency
If match, increment count

🧰 2. Choose Tools

• Data Structures: HashMap (Counter from collections)
• Technique: Sliding window, Frequency comparison

🧪 3. Dry Run with Mini Input

• s = “abcbac”, p = “abc”
• Window: “abc” → match → count = 1
• Window: “bcb” → no match
• Window: “cba” → match → count = 2

💻 4. Code

from collections import Counter

def count_anagrams(s, p):
    len_p = len(p)
    p_count = Counter(p)
    s_count = Counter()
    result = 0

    for i in range(len(s)):
        s_count[s[i]] += 1
        if i >= len_p:
            s_count[s[i-len_p]] -= 1
            if s_count[s[i-len_p]] == 0:
                del s_count[s[i-len_p]]
        if s_count == p_count:
            result += 1

    return result

print(count_anagrams("cbaebabacd", "abc"))

✅ 5. Test & Debug

• Add print statements for sliding window and counters
• Edge case: s = “aaaaa”, p = “a” → 5 matches

🧠 Optional Enhancements

• Use == for Counter comparison
• Time: O(n), Space: O(1) since 26 letters only

Problem 4: Longest Substring with K Distinct Characters

🧠 0. Understand the Problem

• Problem Statement: Find the length of the longest substring with exactly K distinct characters.
• Input: s = “eceba”, k = 2 → Output: 3 (“ece”)
• Constraints: 1 ≤ s.length ≤ 5 * 10^4
• Keywords: Substring, Distinct Count, Sliding Window

✏️ 1. Write Pseudocode

Initialize left pointer, hashmap to store character counts
Expand right pointer
    add character to hashmap
    if size > K, shrink window from left
Track max length

🧰 2. Choose Tools

• HashMap for char counts
• Sliding window technique

🧪 3. Dry Run

• s = “abcba”, k=2
• “ab” → valid
• “abc” → shrink to “bc”
• “bcb” → valid, max = 3

💻 4. Code

def longest_k_distinct(s, k):
    from collections import defaultdict
    left = 0
    count = defaultdict(int)
    max_len = 0

    for right in range(len(s)):
        count[s[right]] += 1
        while len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)

    return max_len

print(longest_k_distinct("eceba", 2))

✅ 5. Test & Debug

• Edge case: s = “aa”, k = 1 → Output = 2
• Use print(count) to debug shrinking

🧠 Enhancements

• Time: O(n), Space: O(k)

Problem 5: Longest Repeating Character Replacement

🧠 0. Understand the Problem

• Problem Statement: Replace at most k characters in string s to make longest repeating character substring.
• Input: s = “ABAB”, k = 2 → Output = 4
• Constraints: Only uppercase letters
• Keywords: Frequency, Max Replace

✏️ 1. Pseudocode

Sliding window, count frequency of chars
Keep max_freq
If (window size - max_freq) > k → shrink window

🧰 2. Choose Tools

• HashMap
• Sliding window

💻 4. Code

def character_replacement(s, k):
    from collections import defaultdict
    count = defaultdict(int)
    max_len = 0
    max_freq = 0
    left = 0

    for right in range(len(s)):
        count[s[right]] += 1
        max_freq = max(max_freq, count[s[right]])

        if (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

print(character_replacement("ABAB", 2))

🧠 Enhancements

• Optimize by tracking max_freq

Problem 6: Permutation in String

🧠 0. Understand the Problem

• Problem Statement: Check if s2 contains a permutation of s1.
• Input: s1 = “ab”, s2 = “eidbaooo” → Output: True
• Keywords: Anagram match

✏️ 1. Pseudocode

Compare frequency of s1 and current window of size len(s1)

💻 Code

from collections import Counter

def check_inclusion(s1, s2):
    len1 = len(s1)
    s1_count = Counter(s1)
    s2_count = Counter()

    for i in range(len(s2)):
        s2_count[s2[i]] += 1
        if i >= len1:
            s2_count[s2[i - len1]] -= 1
            if s2_count[s2[i - len1]] == 0:
                del s2_count[s2[i - len1]]
        if s1_count == s2_count:
            return True
    return False

print(check_inclusion("ab", "eidbaooo"))

✅ 5. Test

• Use frequency count and comparison

Pages: 1 2