Sliding Window Pattern in Hindi (Hinglish): Free Guide

Hindi mein samjho (Hinglish)

Neeche is topic ka Hinglish explanation hai, wahi jo hamare course lesson mein audio narration ke saath chalta hai. Code English mein hai, samjhana Hindi mein.

Longest Substring Without Repeating Characters

Yeh variable-size sliding window ka template problem hai. Bangalore mein har interviewer jo string questions poochta hai, uske paas iska koi version zaroor hai. Iss ek ko cleanly solve kar lo, toh yahi pattern tumhe disguise mein dikhega: longest repeating character replacement, minimum window substring, permutation in string aur dher saare aur problems mein.

Pattern recognition. Jab bhi question pochhe sabse lamba ya sabse chhota contiguous run jo koi condition satisfy karta ho, pehla khayaal sliding window ka aana chahiye. Window mein do pointers hote hain, left aur right. Right pointer ek-ek step window expand karta hai. Left pointer tab contract karta hai jab window condition violate kar de. Bas yahi template hai.

Asli unlock. Brute force har left position ke liye scratch se restart karta hai. Bekaar hai. Iske bajaay, ek hi window rakho aur dono ends sirf aage badhao: kabhi peeche nahi. Right pointer ek character add karta hai. Agar woh duplicate banaye, toh left pointer aage slide karo jab tak duplicate na hate. Har character window mein ek baar enter hota hai aur zyada se zyada ek baar leave karta hai. Yahi O of n total work hai.

Python solution: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    seen = set()
    l = 0
    best = 0
    for r in range(len(s)):
        while s[r] in seen:
            seen.remove(s[l])
            l += 1
        seen.add(s[r])
        best = max(best, r - l + 1)
    return best

Complexity: Brute force (restart from each index): time O(n²), space O(min(n, alphabet)); Sliding window with hash set: time O(n), space O(min(n, alphabet)).

Permutation in String

Permutation in String string puzzle jaisa lagta hai. Asli mein yeh sliding window problem hai disguise mein. Specifically FIXED-size template: window kabhi grow ya shrink nahi karta, bas slide karta hai. Aaj yeh trick lock karo aur teen aur LeetCode mediums trivial ho jaate hain.

Yeh FIXED-size sliding window pattern hai. Window humesha exactly len of s1 characters wide hota hai. Tum usko ek-ek step s2 ke across slide karte ho aur har position pe pochte ho: kya iss window ki character frequency s1 ke equal hai? Haan toh true return karo. Window size hi constraint hai.

Unlock do layers deep hai. Layer ek: s1 ke liye 26-slot frequency array banao, current window ke liye doosra 26-slot array maintain karo. Jab window ek step slide hota hai, tum sirf right mein ek character add karte ho aur left mein ek drop karte ho: O of 1 kaam, na ki O of k. Layer do: har step pe dono 26-arrays compare karna bhi waste hai. Ek matches counter track karo jo bataye 26 letters mein se kitne abhi agree karte hain. Jab matches 26 ke equal ho jaaye, permutation mil gaya.

Python solution: Permutation in String

def check_inclusion(s1, s2):
    if len(s1) > len(s2): return False
    s1c = [0]*26; win = [0]*26
    for i in range(len(s1)):
        s1c[ord(s1[i]) - 97] += 1
        win[ord(s2[i]) - 97] += 1
    matches = sum(1 for i in range(26) if s1c[i] == win[i])
    l = 0
    for r in range(len(s1), len(s2)):
        if matches == 26: return True
        a = ord(s2[r]) - 97
        win[a] += 1
        if win[a] == s1c[a]: matches += 1
        elif win[a] == s1c[a] + 1: matches -= 1
        b = ord(s2[l]) - 97
        win[b] -= 1
        if win[b] == s1c[b]: matches += 1
        elif win[b] == s1c[b] - 1: matches -= 1
        l += 1
    return matches == 26

Complexity: Brute force (sort every window): time O(n · k log k), space O(k); Sliding window + freq compare each slide: time O(n · 26) = O(n), space O(26) = O(1); Sliding window + matches counter (optimal): time O(n), space O(1).

Minimum Window Substring

Welcome to Minimum Window Substring: sliding window family ka sabse mushkil problem aur Google, Amazon, Adobe ka classic onsite question. Fixed-size sliding window aasaan hai. Yeh variable-size sliding window hai jahan dono pointers independently move karte hain. Pattern aaj theek se aa gaya toh aadha dozen Hard problems unlock ho jaate hain, sab same code skeleton reuse karte hain.

Pattern recognition. Jab bhi problem kahe "s ka smallest ya largest substring jo target ke against condition C satisfy karta hai," aur condition character frequencies pe depend kare: wahi variable-size sliding window hai. Right pointer expand karta hai aur sirf add karta hai. Left pointer shrink karta hai aur sirf remove karta hai. Har pointer at most n baar move karta hai, total O of n.

Asli unlock. Dekho jab tum left pointer ek position shrink karte ho, naya window purana window minus ek character hai. Sab kuch dobara compute karne ki zaroorat nahi. Do hash maps rakho, need t se, have current window se, aur ek counter called formed jo track karta hai kitne unique characters in need abhi fully met hain. Formed increment karo jab koi character pehli baar apna quota poora karta hai, decrement karo jab neeche girta hai. Window valid hai jab formed equals required.

Python solution: Minimum Window Substring

def min_window(s, t):
    if not t or not s or len(t) > len(s): return ""
    need = {}
    for c in t: need[c] = need.get(c, 0) + 1
    required = len(need)
    have = {}
    formed = 0
    l = 0
    best = (-1, 0, 0)  # (length, l, r)
    for r in range(len(s)):
        c = s[r]
        if c in need:
            have[c] = have.get(c, 0) + 1
            if have[c] == need[c]:
                formed += 1
        while formed == required:
            if best[0] == -1 or (r - l + 1) < best[0]:
                best = (r - l + 1, l, r)
            cl = s[l]
            if cl in need:
                have[cl] -= 1
                if have[cl] < need[cl]:
                    formed -= 1
            l += 1
    return "" if best[0] == -1 else s[best[1]:best[2]+1]

Complexity: Brute force (every (i, j) + per-step coverage check): time O(n² · m), space O(m); Sliding window with formed counter: time O(n + m), space O(m).