JavaScript-এ স্লাইডিং উইন্ডো অ্যালগরিদম ব্যবহার করে ম্যাক্স স্লাইস খুঁজে বের করা

ভূমিকা

এই সমস্যায় একটি অ্যারে দেওয়া আছে, যেখানে সর্বোচ্চ দৈর্ঘ্যের সাবঅ্যারে (slice) খুঁজে বের করতে হবে যাতে সেটিতে **সর্বোচ্চ দুটি ভিন্ন সংখ্যা** থাকে। এটি ক্লাসিক স্লাইডিং উইন্ডো (Sliding Window) অ্যালগরিদম সমস্যা।

সম্পূর্ণ কোড

const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8];

const map = { length: 0 };
let required = [];

for (let start = 0, end = 0; end <= arr.length; ) {
  if (map.length > 2) {
    // উইন্ডো ছোট করুন (start বাড়ান)
    if (map[arr[start]] === 1) {
      delete map[arr[start]];
      map.length--;
    } else {
      map[arr[start]]--;
    }
    start++;
  } else {
    // উইন্ডো বড় করুন (end বাড়ান)
    if (end - start > required.length) {
      required = arr.slice(start, end);
    }
    if (map[arr[end]]) {
      map[arr[end]]++;
    } else {
      map[arr[end]] = 1;
      map.length++;
    }
    end++;
  }
}

console.log(required);

আউটপুট

[1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8]

এই সাবঅ্যারেতে শুধু `1` এবং `8` দুটি ভিন্ন সংখ্যা আছে এবং এর দৈর্ঘ্য ১১, যা সর্বোচ্চ।

স্লাইডিং উইন্ডো অ্যালগরিদম ব্যাখ্যা

কনসেপ্ট

• দুটি পয়েন্টার: start (উইন্ডোর শুরু) এবং end (উইন্ডোর শেষ)
• একটি ম্যাপ/অবজেক্ট: উইন্ডোর ভিতরের প্রতিটি সংখ্যার ফ্রিকোয়েন্সি ট্র্যাক করে
• map.length: উইন্ডোর ভিতরে কতগুলো **ভিন্ন** সংখ্যা আছে তা ট্র্যাক করে

অ্যালগরিদম ফ্লো

1. প্রসার (Expand): `end` বাড়িয়ে উইন্ডো বড় করুন যতক্ষণ না ভিন্ন সংখ্যা ২টি ছাড়া
2. রেকর্ড: প্রতিটি বৈধ উইন্ডোর জন্য, যদি দৈর্ঘ্য বড় হয় তবে `required` আপডেট করুন
3. সংকোচন (Shrink): যখন ভিন্ন সংখ্যা ২টি ছাড়া, `start` বাড়িয়ে উইন্ডো ছোট করুন
4. পুনরাবৃত্তি: `end` অ্যারের শেষ পর্যন্ত পৌঁছাতে পর্যন্ত চালিয়ে যান

টাইম ও স্পেস কমপ্লেক্সিটি

• Time: O(n) - প্রতিটি এলিমেন্টสูงোsters একবার ভিজিট করা হয়
• Space: O(k) - এখানে k=২ (ভিন্ন সংখ্যা), সাধারণত O(1)

সাধারণ স্লাইডিং উইন্ডো টেমপ্লেট

function slidingWindow(arr, condition) {
  let start = 0, maxLen = 0, result = [];
  const map = {};
  
  for (let end = 0; end < arr.length; end++) {
    // ১. end এলিমেন্ট যোগ করুন
    addToWindow(arr[end]);
    
    // ২. কন্ডিশন ভাঙলে start বাড়ান
    while (!condition(map)) {
      removeFromWindow(arr[start]);
      start++;
    }
    
    // ৩. রেজাল্ট আপডেট
    if (end - start + 1 > maxLen) {
      maxLen = end - start + 1;
      result = arr.slice(start, end + 1);
    }
  }
  return result;
}

সমস্যার ভেরিয়েশন

• Exact K distinct: ঠিক K টি ভিন্ন সংখ্যা
• At most K distinct: সর্বোচ্চ K টি ভিন্ন সংখ্যা (এই সমস্যা)
• Longest substring without repeating: ক্যারেক্টার версия
• Minimum window substring: টার্গেট স্ট্রিং কভার করতে মিনিমাম উইন্ডো

সারাংশ

স্লাইডিং উইন্ডো অ্যালগরিদম সাবঅ্যারে/সাবস্ট্রিং সমস্যার জন্য অত্যন্ত দক্ষ। দুটি পয়েন্টার এবং ফ্রিকোয়েন্সি ম্যাপ ব্যবহার করে O(n) টাইমে সমাধান করা যায়।