Sliding window algorithm in bangla : easy for all

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

স্বাগতম! এই ব্লগে আমরা আলোচনা করবো স্লাইডিং উইন্ডো অ্যালগরিদম সম্পর্কে, যা প্রোগ্রামিং এবং অ্যালগরিদম সমাধানে একটি অত্যন্ত কার্যকরী টেকনিক। এটি কী, কীভাবে কাজ করে, কোথায় ব্যবহৃত হয়, এবং পাইথন ও সি++ এর একাধিক উদাহরণ সহ বিস্তারিতভাবে বাংলায় ব্যাখ্যা করা হবে।

স্লাইডিং উইন্ডো অ্যালগরিদম কী?

স্লাইডিং উইন্ডো হলো একটি অ্যালগরিদম টেকনিক যা একটি নির্দিষ্ট বা পরিবর্তনশীল আকারের "উইন্ডো" ব্যবহার করে ডেটা (যেমন অ্যারে বা স্ট্রিং) প্রক্রিয়া করে। এই উইন্ডোটি ডেটার উপর দিয়ে স্লাইড করে এবং প্রতিটি ধাপে নির্দিষ্ট কাজ সম্পন্ন করে। এটি সময় জটিলতা কমাতে অত্যন্ত কার্যকর।

এটি কীভাবে কাজ করে?

স্লাইডিং উইন্ডো টেকনিক প্রধানত দুই ধরনের হয়:

• নির্দিষ্ট আকারের উইন্ডো (Fixed Size Window): উইন্ডোর আকার স্থির থাকে।
• পরিবর্তনশীল আকারের উইন্ডো (Variable Size Window): উইন্ডোর আকার প্রয়োজন অনুযায়ী পরিবর্তিত হয়।

এটি ডেটার একটি অংশ প্রক্রিয়া করে এবং তারপর উইন্ডোটি সামনে সরিয়ে পরবর্তী অংশে যায়।

কোথায় ব্যবহৃত হয়?

স্লাইডিং উইন্ডো বিভিন্ন প্রোগ্রামিং সমস্যায় ব্যবহৃত হয়, যেমন:

• সর্বাধিক বা সর্বনিম্ন উপ-অ্যারে খুঁজে বের করা।
• নির্দিষ্ট যোগফলের উপ-অ্যারে খুঁজে পাওয়া।
• স্ট্রিং-এ প্যাটার্ন ম্যাচিং।
• ডেটা স্ট্রিম প্রক্রিয়াকরণ।

উদাহরণ ১: নির্দিষ্ট আকারের উইন্ডো (সর্বাধিক যোগফল)

ধরা যাক, আমাদের অ্যারে [1, -3, 2, 1, -1, 4] এবং আমরা ৩টি উপাদানের সর্বাধিক যোগফল চাই।

পাইথন কোড

arr = [1, -3, 2, 1, -1, 4]
k = 3  # উইন্ডোর আকার
max_sum = float('-inf')

for i in range(len(arr) - k + 1):
    window_sum = sum(arr[i:i + k])
    max_sum = max(max_sum, window_sum)
    print(f"উইন্ডো {i+1}: {arr[i:i + k]}, যোগফল: {window_sum}")

print(f"সর্বাধিক যোগফল: {max_sum}")
        

সি++ কোড

#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -3, 2, 1, -1, 4};
    int k = 3;
    int max_sum = INT_MIN;

    for (int i = 0; i <= arr.size() - k; i++) {
        int window_sum = 0;
        for (int j = i; j < i + k; j++) {
            window_sum += arr[j];
        }
        max_sum = max(max_sum, window_sum);
        cout << "উইন্ডো " << i + 1 << ": ";
        for (int j = i; j < i + k; j++) cout << arr[j] << " ";
        cout << ", যোগফল: " << window_sum << endl;
    }
    cout << "সর্বাধিক যোগফল: " << max_sum << endl;
    return 0;
}
        

আউটপুট:

উইন্ডো 1: [1, -3, 2], যোগফল: 0
উইন্ডো 2: [-3, 2, 1], যোগফল: 0
উইন্ডো 3: [2, 1, -1], যোগফল: 2
উইন্ডো 4: [1, -1, 4], যোগফল: 4
সর্বাধিক যোগফল: 4
        

উদাহরণ ২: পরিবর্তনশীল আকারের উইন্ডো (নির্দিষ্ট যোগফল)

ধরা যাক, অ্যারে [1, -1, 2, 3, -2, 4] এবং আমরা যোগফল ৫ চাই।

পাইথন কোড

arr = [1, -1, 2, 3, -2, 4]
target = 5
curr_sum = 0
start = 0

for end in range(len(arr)):
    curr_sum += arr[end]
    while curr_sum > target and start <= end:
        curr_sum -= arr[start]
        start += 1
    if curr_sum == target:
        print(f"উপ-অ্যারে: {arr[start:end+1]}, যোগফল: {curr_sum}")
        

সি++ কোড

#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -1, 2, 3, -2, 4};
    int target = 5;
    int curr_sum = 0, start = 0;

    for (int end = 0; end < arr.size(); end++) {
        curr_sum += arr[end];
        while (curr_sum > target && start <= end) {
            curr_sum -= arr[start];
            start++;
        }
        if (curr_sum == target) {
            cout << "উপ-অ্যারে: [";
            for (int i = start; i <= end; i++) {
                cout << arr[i] << (i < end ? ", " : "");
            }
            cout << "], যোগফল: " << curr_sum << endl;
        }
    }
    return 0;
}
        

আউটপুট:

উপ-অ্যারে: [2, 3], যোগফল: 5
        

উদাহরণ ৩: স্ট্রিং-এ স্লাইডিং উইন্ডো (দীর্ঘতম সাবস্ট্রিং)

ধরা যাক, স্ট্রিং "abcabcbb" এবং আমরা দীর্ঘতম সাবস্ট্রিং চাই যেখানে কোনো অক্ষর পুনরাবৃত্তি নেই।

পাইথন কোড

s = "abcabcbb"
char_map = {}
start = 0
max_length = 0
max_substring = ""

for end in range(len(s)):
    if s[end] in char_map and char_map[s[end]] >= start:
        start = char_map[s[end]] + 1
    else:
        if end - start + 1 > max_length:
            max_length = end - start + 1
            max_substring = s[start:end + 1]
    char_map[s[end]] = end

print(f"দীর্ঘতম সাবস্ট্রিং: {max_substring}, দৈর্ঘ্য: {max_length}")
        

সি++ কোড

#include 
#include 
#include 
using namespace std;

int main() {
    string s = "abcabcbb";
    unordered_map char_map;
    int start = 0, max_length = 0;
    string max_substring;

    for (int end = 0; end < s.length(); end++) {
        if (char_map.find(s[end]) != char_map.end() && char_map[s[end]] >= start) {
            start = char_map[s[end]] + 1;
        } else if (end - start + 1 > max_length) {
            max_length = end - start + 1;
            max_substring = s.substr(start, max_length);
        }
        char_map[s[end]] = end;
    }

    cout << "দীর্ঘতম সাবস্ট্রিং: " << max_substring << ", দৈর্ঘ্য: " << max_length << endl;
    return 0;
}
        

আউটপুট:

দীর্ঘতম সাবস্ট্রিং: abc, দৈর্ঘ্য: 3
        

সুবিধা ও অসুবিধা

সুবিধা:

• সময় জটিলতা কমায় (O(n²) থেকে O(n))।
• বাস্তবায়ন সহজ এবং বোঝা যায়।
• অ্যারে ও স্ট্রিং উভয় ক্ষেত্রেই কার্যকর।

অসুবিধা:

• সব সমস্যার জন্য উপযুক্ত নয়।
• কিছু ক্ষেত্রে অতিরিক্ত মেমোরি লাগতে পারে।

উপসংহার

স্লাইডিং উইন্ডো অ্যালগরিদম প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি শক্তিশালী এবং জনপ্রিয় টেকনিক। এই ব্লগে আমরা এটির বিস্তারিত ব্যাখ্যা, পাইথন ও সি++ এর উদাহরণ, এবং এর প্রয়োগ দেখেছি। এটি শিখে আপনি অনেক জটিল সমস্যা সহজে সমাধান করতে পারবেন।

স্লাইডিং উইন্ডো প্র্যাকটিস প্রবলেম

এখানে কিছু জনপ্রিয় প্রোগ্রামিং প্ল্যাটফর্ম থেকে স্লাইডিং উইন্ডো সম্পর্কিত সমস্যার লিঙ্ক দেওয়া হলো। এগুলো অনুশীলন করে আপনি আপনার দক্ষতা বাড়াতে পারেন।

• CodeChef: Maximum Subarray Sum with K Elements
• CodeChef: Chef and Subarray
• Codeforces: Longest k-Good Segment
• Codeforces: Subarray Counting
• LeetCode: Maximum Average Subarray I
• LeetCode: Longest Substring Without Repeating Characters
• LeetCode: Sliding Window Maximum
• LeetCode: Minimum Size Subarray Sum