Sliding Window

दाएँ बढ़ाएँ, बाएँ घटाएँ

"सबसे लंबा/छोटा/सर्वश्रेष्ठ सन्निहित subarray या substring" समस्याओं के लिए: नया तत्व शामिल करने को right हिलाएँ; जब तक खिड़की बाधा तोड़े, तत्व हटाने को left हिलाएँ। हर इंडेक्स एक बार आता-जाता है — O(n)।

बिना दोहराव सबसे लंबा substring

हर वर्ण का अंतिम इंडेक्स ट्रैक करें; किसी दोहराव से आगे left कूदें।

def longest_unique(s):
    last = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best

Output:

longest_unique("abcabcbb") -> 3   ("abc")

इसे पहचानना

कीवर्ड: "सन्निहित", "subarray/substring", "अधिकतम K", "योग बराबर", "सबसे लंबा/छोटा"। निश्चित-आकार खिड़की और भी सरल — एक से सरकाएँ और चलती राशि समायोजित करें।