Sliding Window

আগের position-এর কাজটা আবার করার বদলে সেটাই কাজে লাগান।

মূল ধারণা

ভাবুন আপনি রাস্তা ধরে হাঁটছেন আর একটা frame দিয়ে একসাথে 3টা বাড়ি দেখা যাচ্ছে। এক ধাপ এগোনোর পর দৃশ্যমান বাড়িগুলোর মোট দাম জানতে 3টা বাড়ি নতুন করে যোগ করার দরকার নেই: যে নতুন বাড়িটা এল সেটা যোগ করুন আর যেটা বেরিয়ে গেল সেটা বাদ দিন।

Window বড় আর ছোটও হতে পারে: “কোনো অক্ষর repeat না হওয়া সবচেয়ে লম্বা অংশ” খুঁজতে ডান প্রান্ত একটা একটা করে অক্ষর এগোয়, আর repeat ধরা পড়লে বাঁ প্রান্ত ততটুকু সামনে লাফ দেয় যতটুকুতে repeat-টা সরে যায়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Time complexity: O(n) – প্রতিটা item window-তে একবার ঢোকে আর বড়জোর একবার বেরোয়। Space complexity: O(1) fixed window-এর জন্য; substring version-এ O(alphabet) (শেষ দেখা position-এর map)।