স্লাইডিং-উইন্ডো কৌশল কী?

Question

Accepted Answer

**sliding-window** কৌশল একটি অ্যারে বা স্ট্রিংয়ের উপর একটি সংলগ্ন পরিসীমা (উইন্ডো) বজায় রাখে এবং এটি স্লাইড করে, শুরু থেকে পুনরায় গণনা করার পরিবর্তে, অনেক সাব্যারে/সাবস্ট্রিং সমস্যা **O(n)** এ সমাধান করে।

## ধারণা

ডান প্রান্তটি সরিয়ে উইন্ডোটি প্রসারিত করুন; যখন কোনো সীমাবদ্ধতা লঙ্ঘিত হয় তখন বাম প্রান্তটি সরিয়ে এটি সংকুচিত করুন। পুনরায় স্ক্যান করার পরিবর্তে পূর্ববর্তী গণনা পুনরায় ব্যবহার করুন।

## উদাহরণ: আকার k এর যেকোনো উইন্ডোর সর্বাধিক যোগফল

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## জটিলতা

- **সময়:** O(n) — প্রতিটি উপাদান উইন্ডো থেকে একবার প্রবেশ এবং ত্যাগ করে।
- **স্থান:** স্থির উইন্ডোগুলির জন্য O(1), বিষয়বস্তু ট্র্যাক করার সময় O(k)।

## কখন ব্যবহার করতে হবে / সাধারণ ত্রুটি

"সম্পত্তি X সহ দীর্ঘতম/সংক্ষিপ্ততম/সর্বাধিক সাব্যারে" সমস্যাগুলির জন্য ব্যবহার করুন। **পরিবর্তনশীল** উইন্ডোগুলির জন্য, সীমাবদ্ধতা পুনরুদ্ধার করতে বাম পয়েন্টারটি এগিয়ে নিন। সীমানা উপাদান যোগ/সরানোর সময় off-by-one ত্রুটিগুলিতে সাবধান থাকুন।

## কেন এটি গুরুত্বপূর্ণ

স্লাইডিং উইন্ডো অপ্রয়োজনীয় কাজ দূর করে, O(n·k) পুনর্গণনাকে একটি পাসে পরিণত করে।

এটি সাবস্ট্রিং এবং সাব্যারে সমস্যাগুলির জন্য যাওয়ার ধরণ যা সাক্ষাৎকারে ক্রমাগত উপস্থিত হয়।

অন্তর্দৃষ্টি — পূর্ববর্তী ফলাফল পুনরায় ব্যবহার করুন পুনর্গণনার পরিবর্তে — স্ট্রিমিং এবং রিয়েল-টাইম ডেটায় সাধারণীকৃত হয়।