ভূমিকা

Sliding Window হলো একটি শক্তিশালী algorithmic technique যা array বা string-এর উপর contiguous subarray বা substring নিয়ে কাজ করে। এই technique-এ একটি window ধীরে ধীরে সরিয়ে নেওয়া হয়, এবং nested loop ব্যবহার না করে O(n) সময়ে সমস্যা সমাধান করা যায়।

সমস্যা ১: Maximum Sum Subarray of Size K (নির্দিষ্ট আকারের সর্বোচ্চ যোগফলের Subarray)

সমস্যার বিবরণ

একটি integer array nums এবং একটি positive integer k দেওয়া আছে। k আকারের সব subarray-এর মধ্যে সর্বোচ্চ যোগফল বের করতে হবে।

উদাহরণ:

• Input: nums = [2, 1, 5, 1, 3, 2], k = 3
• Output: 9
• কারণ: [5, 1, 3] এর যোগফল = 9, যা সবচেয়ে বেশি
• Input: nums = [2, 3, 4, 1, 5], k = 2
• Output: 7
• কারণ: [3, 4] এর যোগফল = 7

চিন্তার পদ্ধতি

Fixed-size Sliding Window ব্যবহার করব। প্রথমে প্রথম kটি element-এর যোগফল বের করব। তারপর window সরানোর সময় নতুন element যোগ করব এবং পুরনো element বাদ দেব। প্রতিটি step-এ maximum track করব।

সমাধান (Java)

public class MaxSumSubarrayOfSizeK {
    public int maxSum(int[] nums, int k) {
        if (nums == null || nums.length < k) return -1;

        int windowSum = 0;
        int maxSum = 0;

        // প্রথম window-এর যোগফল বের করি
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        maxSum = windowSum;

        // Window slide করি — নতুন element যোগ, পুরনো element বাদ
        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k]; // right থেকে যোগ, left থেকে বাদ
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        MaxSumSubarrayOfSizeK solution = new MaxSumSubarrayOfSizeK();
        System.out.println(solution.maxSum(new int[]{2, 1, 5, 1, 3, 2}, 3)); // Output: 9
        System.out.println(solution.maxSum(new int[]{2, 3, 4, 1, 5}, 2));    // Output: 7
        System.out.println(solution.maxSum(new int[]{-1, -2, -3, -4}, 2));   // Output: -3
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)

---

সমস্যা ২: Longest Substring with At Most K Distinct Characters

সমস্যার বিবরণ

একটি string s এবং একটি integer k দেওয়া আছে। সর্বোচ্চ kটি distinct character আছে এমন সবচেয়ে দীর্ঘ substring-এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ:

• Input: s = "eceba", k = 2
• Output: 3
• কারণ: "ece" হলো সবচেয়ে দীর্ঘ substring যেখানে মাত্র 2টি distinct character (e, c)
• Input: s = "aa", k = 1
• Output: 2

চিন্তার পদ্ধতি

Variable-size Sliding Window এবং HashMap ব্যবহার করব। right pointer বাড়াবো এবং character frequency track করব। Window-এ distinct character-এর সংখ্যা k ছাড়িয়ে গেলে left pointer সরিয়ে window ছোট করব।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return 0;

        Map<Character, Integer> charCount = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);

            // Right character window-এ যোগ করি
            charCount.put(rightChar, charCount.getOrDefault(rightChar, 0) + 1);

            // Distinct character k-এর বেশি হলে left সরাই
            while (charCount.size() > k) {
                char leftChar = s.charAt(left);
                charCount.put(leftChar, charCount.get(leftChar) - 1);
                if (charCount.get(leftChar) == 0) {
                    charCount.remove(leftChar); // distinct character সরিয়ে দাও
                }
                left++;
            }

            // সর্বোচ্চ দৈর্ঘ্য আপডেট করি
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstringKDistinct solution = new LongestSubstringKDistinct();
        System.out.println(solution.lengthOfLongestSubstringKDistinct("eceba", 2)); // Output: 3
        System.out.println(solution.lengthOfLongestSubstringKDistinct("aa", 1));    // Output: 2
        System.out.println(solution.lengthOfLongestSubstringKDistinct("aabbcc", 2)); // Output: 4
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(k)

---

সমস্যা ৩: Minimum Window Substring

সমস্যার বিবরণ

দুটি string s এবং t দেওয়া আছে। s-এর সবচেয়ে ছোট window (substring) খুঁজে বের করতে হবে যেটিতে t-এর সব character অন্তর্ভুক্ত থাকে। যদি কোনো valid window না থাকে তাহলে "" return করতে হবে।

উদাহরণ:

• Input: s = "ADOBECODEBANC", t = "ABC"
• Output: "BANC"
• কারণ: "BANC" সবচেয়ে ছোট window যেখানে A, B, C সবই আছে
• Input: s = "a", t = "a"
• Output: "a"

চিন্তার পদ্ধতি

Variable Sliding Window এবং দুটি HashMap ব্যবহার করব। t-এর character frequency রাখব। right বাড়িয়ে valid window তৈরি করব। Window valid হলে left সরিয়ে minimum খুঁজব।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        // t-এর character frequency count
        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }

        int required = tCount.size(); // t-তে unique character সংখ্যা
        int formed = 0;               // window-এ desired frequency-র character সংখ্যা

        Map<Character, Integer> windowCount = new HashMap<>();
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);

            // এই character-এর frequency t-এর মতো হয়েছে কিনা চেক করি
            if (tCount.containsKey(c) && windowCount.get(c).intValue() == tCount.get(c).intValue()) {
                formed++;
            }

            // Window valid — left সরিয়ে minimum খুঁজি
            while (formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }

                char leftChar = s.charAt(left);
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                if (tCount.containsKey(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
                    formed--;
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }

    public static void main(String[] args) {
        MinimumWindowSubstring solution = new MinimumWindowSubstring();
        System.out.println(solution.minWindow("ADOBECODEBANC", "ABC")); // Output: "BANC"
        System.out.println(solution.minWindow("a", "a"));               // Output: "a"
        System.out.println(solution.minWindow("a", "b"));               // Output: ""
    }
}

সময় জটিলতা: O(|s| + |t|) | স্থান জটিলতা: O(|s| + |t|)

---

সমস্যা ৪: Fruits Into Baskets (At Most 2 Distinct Fruits)

সমস্যার বিবরণ

একটি integer array fruits দেওয়া আছে যেখানে fruits[i] হলো i-তম গাছে কোন ধরনের ফল আছে। দুটি basket নিয়ে একটানা গাছ থেকে ফল সংগ্রহ করতে হবে। প্রতিটি basket-এ শুধু একই ধরনের ফল রাখা যাবে। সর্বোচ্চ কতটি ফল সংগ্রহ করা যায় তা বের করতে হবে।

উদাহরণ:

• Input: fruits = [1, 2, 1]
• Output: 3 (সব ফল নেওয়া যায়)
• Input: fruits = [0, 1, 2, 2]
• Output: 3
• কারণ: [1, 2, 2] — দুই ধরনের ফল (1 এবং 2) এবং সর্বোচ্চ 3টি

চিন্তার পদ্ধতি

এটি মূলত "At Most 2 Distinct Characters সহ সবচেয়ে দীর্ঘ Subarray" সমস্যা। Sliding Window এবং HashMap দিয়ে সর্বোচ্চ 2 ধরনের fruit রাখব।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class FruitsIntoBaskets {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> basket = new HashMap<>(); // fruit type -> count
        int left = 0;
        int maxFruits = 0;

        for (int right = 0; right < fruits.length; right++) {
            // Right fruit basket-এ রাখি
            basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);

            // Basket-এ 2-এর বেশি type হলে left সরাই
            while (basket.size() > 2) {
                basket.put(fruits[left], basket.get(fruits[left]) - 1);
                if (basket.get(fruits[left]) == 0) {
                    basket.remove(fruits[left]); // এই fruit type শেষ, basket থেকে বাদ
                }
                left++;
            }

            // সর্বোচ্চ ফলের সংখ্যা আপডেট
            maxFruits = Math.max(maxFruits, right - left + 1);
        }

        return maxFruits;
    }

    public static void main(String[] args) {
        FruitsIntoBaskets solution = new FruitsIntoBaskets();
        System.out.println(solution.totalFruit(new int[]{1, 2, 1}));       // Output: 3
        System.out.println(solution.totalFruit(new int[]{0, 1, 2, 2}));    // Output: 3
        System.out.println(solution.totalFruit(new int[]{1, 2, 3, 2, 2})); // Output: 4
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(1) (basket-এ সর্বোচ্চ 3টি entry)

---

সমস্যা ৫: Longest Repeating Character Replacement

সমস্যার বিবরণ

একটি uppercase string s এবং integer k দেওয়া আছে। সর্বোচ্চ kটি character পরিবর্তন করে সবচেয়ে দীর্ঘ substring তৈরি করতে হবে যেখানে সব character একই। এই দীর্ঘতম substring-এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ:

• Input: s = "ABAB", k = 2
• Output: 4
• কারণ: 2টি A বা B পরিবর্তন করলে সম্পূর্ণ string একই character হয়
• Input: s = "AABABBA", k = 1
• Output: 4
• কারণ: index 4 থেকে "ABBA" তে 1টি পরিবর্তন করে "AAAA" বা "BBBB" পাওয়া যায়

চিন্তার পদ্ধতি

Sliding Window ব্যবহার করব। Window-এর সর্বোচ্চ frequency character track করব (maxFreq)। যদি window size - maxFreq > k হয় তাহলে আমাদের k-এর বেশি replacement দরকার — তখন left সরাতে হবে। Window কখনো ছোট হয় না, শুধু বড় বা সমান থাকে।

সমাধান (Java)

public class LongestRepeatingCharacterReplacement {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26]; // প্রতিটি character-এর frequency
        int left = 0;
        int maxFreq = 0; // window-এর সবচেয়ে বেশি আসা character-এর frequency
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            count[idx]++;

            // Window-এর সর্বোচ্চ frequency আপডেট করি
            maxFreq = Math.max(maxFreq, count[idx]);

            // Window valid কিনা চেক: (window size - maxFreq) <= k হলে valid
            int windowSize = right - left + 1;
            if (windowSize - maxFreq > k) {
                // Window invalid — left সরাই
                count[s.charAt(left) - 'A']--;
                left++;
            }

            // Window size কখনো কমে না, তাই সর্বোচ্চ সবসময় বাড়তে থাকে
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestRepeatingCharacterReplacement solution = new LongestRepeatingCharacterReplacement();
        System.out.println(solution.characterReplacement("ABAB", 2));    // Output: 4
        System.out.println(solution.characterReplacement("AABABBA", 1)); // Output: 4
        System.out.println(solution.characterReplacement("AAAA", 2));    // Output: 4
        System.out.println(solution.characterReplacement("ABCDE", 1));   // Output: 2
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)

---

সারসংক্ষেপ

সমস্যা	Window Type	পদ্ধতি	সময় জটিলতা	স্থান জটিলতা
Max Sum Subarray of Size K	Fixed	Simple sliding sum	O(n)	O(1)
Longest Substring K Distinct	Variable	HashMap + shrink	O(n)	O(k)
Minimum Window Substring	Variable	Two HashMaps	O(n)	O(n)
Fruits Into Baskets	Variable	HashMap (≤2 types)	O(n)	O(1)
Longest Repeating Char Replacement	Variable	Count array + maxFreq	O(n)	O(1)

Sliding Window-এর মূল সূত্র: window expand করো right দিয়ে, invalid হলে left সরিয়ে shrink করো। Fixed window-এ size সবসময় একই থাকে, আর variable window-এ condition অনুযায়ী size পরিবর্তন হয়। এই pattern রপ্ত করলে array ও string-এর বেশিরভাগ subarray/substring সমস্যা O(n)-এ সমাধান করা সম্ভব।