အခန်း ၆ - Sliding Window

Sliding Window (ဆလိုက်ဒင်းဝင်းဒိုး) ဆိုတာ Array ဒါမှမဟုတ် String တွေပေါ်မှာ Subarray သို့မဟုတ် Substring တွေနဲ့ ပတ်သက်ပြီး ရှာဖွေတွက်ချက်ရတဲ့ ပုစ္ဆာတွေကို အလွန် လျင်မြန်စွာ ဖြေရှင်းနိုင်တဲ့ နည်းလမ်း (Algorithm Technique) တစ်ခု ဖြစ်ပါတယ်။

ပုံမှန်အားဖြင့် sub-elements တွေကို Nested Loops (Loop ပတ်တာ နှစ်ထပ်) နဲ့ တွက်ချက်မယ်ဆိုရင် Time Complexity ဟာ $O(n^2)$ ကြာမြင့်တတ်ပေမယ့် Sliding Window ကို စနစ်တကျ အသုံးပြုမယ်ဆိုရင် အချိန်ကို $O(n)$ သို့မဟုတ် Linear Time အထိ သိသိသာသာ လျှော့ချနိုင်ပါတယ်။

Sliding Window ၏ အဓိက အယူအဆ (Core Intuition)

Sliding Window ကို နားလည်ဖို့ အလွယ်ဆုံးနည်းက အရွယ်အစားတူတဲ့ အပိုင်းလေးတွေကို ဘယ်လိုမြန်မြန် တွက်မလဲ ဆိုတာကနေ စပါမယ်။

ဥပမာ nums = [5, 2, -1, 0, 3] ဖြစ်ပြီး၊ တစ်ခါကြည့်မယ့် အပိုင်းအရွယ်အစား k = 3 ဖြစ်တယ်ဆိုပါစို့။ မေးခွန်းက ဆက်တိုက်ရှိတဲ့ ဂဏန်း ၃ လုံးအုပ်စုတွေထဲမှာ ပေါင်းလဒ်အများဆုံးက ဘယ်လောက်လဲ ဆိုတာပါ။

အရင်ဆုံး ဖြစ်နိုင်တဲ့ အုပ်စုတွေကို ရှင်းရှင်းလင်းလင်း ကြည့်ပါ။

ရိုးရိုးနည်းလမ်းနဲ့ဆိုရင် အုပ်စုတစ်ခုချင်းစီကို အစကနေ ပြန်ပေါင်းရပါတယ်။ ဒါကြောင့် [5, 2, -1] ပြီးလို့ [2, -1, 0] ကိုတွက်တဲ့အခါ 2 နဲ့ -1 ကို ထပ်ပေါင်းနေရပါတယ်။

Sliding Window နည်းလမ်းကတော့ အဲ့ဒီ ထပ်တွက်နေတဲ့အလုပ်ကို လျှော့တာပါ။ ပထမအုပ်စုရဲ့ ပေါင်းလဒ်ကို 6 လို့ သိပြီးသားဆိုရင် နောက်အုပ်စုကို အစကနေ ပြန်မပေါင်းတော့ပါဘူး။

ဒီလို အရင် window ရဲ့ အဖြေကို သုံးပြီး နောက် window ရဲ့ အဖြေကို တွက်တာ ကို Sliding Window လို့ ခေါ်ပါတယ်။

nextWindowSum = currentWindowSum - ထွက်သွားသောတန်ဖိုး + ဝင်လာသောတန်ဖိုး

အုပ်စုတိုင်းကို အစကနေ ပြန်ပေါင်းရင် $O(n \times k)$ ကြာနိုင်ပေမယ့် Sliding Window နဲ့ဆိုရင် ညာဘက်သို့ တစ်ခါချင်း ရွှေ့သွားရုံဖြစ်လို့ $O(n)$ အထိ လျှော့နိုင်ပါတယ်။

ဝင်းဒိုး အမျိုးအစားများ (Types of Sliding Windows)

Sliding Window ပြဿနာတွေကို အဓိကအားဖြင့် အမျိုးအစား ၂ မျိုး ခွဲခြားနိုင်ပါတယ်။

၁။ Fixed-size Window (ပုံသေအရွယ်အစား ဝင်းဒိုး)

ဝင်းဒိုးရဲ့ အကျယ်ဟာ ပုစ္ဆာမှာ ပေးထားတဲ့အတိုင်း အမြဲတမ်း ပုံသေဖြစ်နေတတ်ပါတယ်။ (ဥပမာ- size က $k$ လို့ ပေးထားခြင်း)။

• လုပ်ဆောင်ပုံ: ပထမဆုံး size $k$ ရှိတဲ့ window တစ်ခု ဆောက်ပါ။ ပြီးရင် ညာဘက်အစွန်းကို တစ်ဆင့်တိုးပြီး ဘယ်ဘက်အစွန်းကိုပါ တစ်ဆင့်လိုက်တိုးကာ window အရွယ်အစား $k$ အတိုင်း မပြောင်းလဲဘဲ ညာဘက်သို့ ဆလိုက်တိုက် ရွှေ့သွားပါ။

၂။ Dynamic-size Window (ပြောင်းလဲနိုင်သော ဝင်းဒိုး)

ဝင်းဒိုးရဲ့ အရွယ်အစားက သတ်မှတ်ထားတဲ့ အခြေအနေပေါ်မူတည်ပြီး အတိုးအလျှော့ ရှိပါတယ်။

• လုပ်ဆောင်ပုံ: left နှင့် right pointer နှစ်ခုကို သုံးပြီး right ကို ရွှေ့ကာ ဝင်းဒိုးကို ချဲ့သွားပါ။ အကယ်၍ သတ်မှတ်ချက် ကျော်လွန်သွားတဲ့အခါ left ကို ညာဘက်သို့ ရွှေ့ပြီး ဝင်းဒိုးကို ပြန်ကျဉ်းစေပါတယ်။ Window မှန်ကန်နေတဲ့အချိန်တိုင်း အဖြေကို update လုပ်သွားပါတယ်။

Two Pointers နဲ့ Sliding Window ဘာကွာလဲ

Sliding Window က Two Pointers (Same Direction) ရဲ့ အထူးပုံစံ တစ်ခုပါ။ နှစ်ခုလုံး left/right pointer သုံးပေမယ့် ရည်ရွယ်ချက် ကွဲပါတယ်။

အလွယ်မှတ်ရင် — pointer ၂ ခုကြားက အပိုင်းတစ်ခုလုံးကို စဉ်းစားဖို့ လိုရင် Sliding Window၊ pointer ၂ ခုရဲ့ နေရာကသာ အရေးကြီးရင် Two Pointers ပါ။

Real-world မှာ ဘယ်လိုသုံးလဲ

Sliding Window က "ဆက်တိုက် N ခု" သို့မဟုတ် "လတ်တလော အချိန်ပိုင်း" ပြဿနာတွေမှာ နေ့စဉ် တွေ့ရပါတယ်။

• Rate limiting — user တစ်ယောက် "၁ မိနစ်အတွင်း request ဘယ်နှစ်ကြိမ်" လုပ်လဲ ရေတွက်ဖို့ — အချိန် window တစ်ခုထဲက request count ကို ထိန်းတယ်။
• လတ်တလော metrics — "နောက်ဆုံး ၇ ရက်အတွင်း visitor အများဆုံး", "နောက်ဆုံး transaction ၁၀ ခု ပျမ်းမျှ" — fixed window။
• Streaming / log analytics — moving average၊ time-series ရဲ့ window aggregate။
• Longest active session — condition မပျက်သရွေ့ window ချဲ့သွားတဲ့ dynamic window။

ဒီ pattern တွေ အကုန်လုံးက အောက်က ပုစ္ဆာတွေနဲ့ သဘောတရားချင်း တူပါတယ်။

Questions

Sliding Window ကို ကျွမ်းကျင်စွာ အသုံးချတတ်စေဖို့ အမေးအများဆုံး မေးခွန်းပုံစံတွေကို တစ်ဆင့်ချင်း လေ့လာကြည့်ရအောင်။ အလွယ်ဆုံး Fixed-size window ကနေ စပါမယ်။

၁။ Maximum Sum Subarray of Size K

ဂဏန်း array nums တစ်ခုနဲ့ window size k ပေးထားတယ်။ ဆက်တိုက်ရှိတဲ့ ဂဏန်း k လုံးအုပ်စုတွေထဲက ပေါင်းလဒ်အများဆုံးကို ရှာပါ။

Example:

Input:  nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: [5, 1, 3] ၏ ပေါင်းလဒ် 9 သည် အများဆုံး ဖြစ်သည်။

ရှင်းလင်းချက်

ဒါက အပေါ်က Core Intuition မှာ ပြောခဲ့တဲ့ Fixed-size window အတိအကျပါ။ window တိုင်းကို အစကနေ ပြန်မပေါင်းဘဲ — ထွက်သွားတဲ့တန်ဖိုး နှုတ်၊ ဝင်လာတဲ့တန်ဖိုး ပေါင်း လုပ်ရုံပါ။ ဒါကြောင့် $O(n)$ ဖြစ်တယ်။

Time Complexity: $O(n)$ — array တစ်ပတ်ပဲ ပတ်ရသည်။
Space Complexity: $O(1)$

class Solution {
    public int maxSumSubarray(int[] nums, int k) {
        int windowSum = 0;
        // ပထမဆုံး window k လုံးကို ပေါင်းသည်
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        int maxSum = windowSum;
        // window ကို တစ်လှမ်းချင်း ရွှေ့သည် — အဟောင်းနှုတ်၊ အသစ်ပေါင်း
        for (int right = k; right < nums.length; right++) {
            windowSum += nums[right] - nums[right - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }
}

၂။ Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the $i^{th}$ day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

ရှင်းလင်းချက်

ရှယ်ယာ (Stock) ဈေးနှုန်းတွေကို နေ့အလိုက် ပေးထားတဲ့ Array တစ်ခု ဖြစ်ပါတယ်။ အကျိုးအမြတ် အများဆုံး (Maximum Profit) ရအောင် ဘယ်နေ့မှာ ဝယ်ပြီး ဘယ်နေ့မှာ ပြန်ရောင်းရမလဲဆိုတာ ရှာရမှာပါ။ စည်းကမ်းချက်ကတော့ မရောင်းခင် အရင်ဝယ်ရမှာ ဖြစ်လို့ နောက်နေ့ဈေးနှုန်းထဲကနေ အရင်နေ့ဈေးနှုန်းကိုပဲ နှုတ်လို့ ရပါမယ်။

ဒီပုစ္ဆာကို Sliding Window / Two Pointers သဘောတရားနဲ့ စဉ်းစားနိုင်ပါတယ်။

• left pointer က ဝယ်တဲ့နေ့ (Buy Day) ကို ညွှန်ပြပြီး၊ right pointer က ရောင်းတဲ့နေ့ (Sell Day) ကို ညွှန်ပြပါမယ်။
• အမြဲတမ်း prices[left] (ဝယ်ဈေး) က prices[right] (ရောင်းဈေး) ထက် သက်သာနေစေချင်ပါတယ်။
• အကယ်၍ prices[left] < prices[right] ဖြစ်နေရင် အကျိုးအမြတ် ရနိုင်တဲ့အတွက် profit ကို တွက်ချက်ပြီး maxProfit ကို Update လုပ်ပါမယ်။
• အကယ်၍ prices[left] >= prices[right] ဖြစ်သွားရင် (ဆိုလိုတာက ရောင်းဈေးက ဝယ်ဈေးထက် ပိုသက်သာနေရင်)၊ အဲ့ဒီ right နေ့ဟာ ပိုပြီးဈေးသက်သာတဲ့ ဝယ်စရာနေ့အသစ် ဖြစ်သွားပါပြီ။ ဒါကြောင့် ဝယ်တဲ့နေ့ pointer ကို left = right ဆိုပြီး ချက်ချင်း ရွှေ့လိုက်ပါမယ်။
• ခြေလှမ်းတိုင်းမှာ right ကို တစ်လှမ်းချင်း တိုးသွားပါမယ်။

Time Complexity: $O(n)$ - Array ကို တစ်ခေါက်ပဲ ပတ်လို့ဖြစ်ပါတယ်။
Space Complexity: $O(1)$ - memory ပိုသုံးစရာ မလိုလို့ ဖြစ်ပါတယ်။

Java Solution

class Solution {
    public int maxProfit(int[] prices) {
        int left = 0; // Buy pointer
        int right = 1; // Sell pointer
        int maxProfit = 0;

        while (right < prices.length) {
            // ဝယ်ဈေးထက် ရောင်းဈေးက ပိုကြီးနေလျှင် (အမြတ်ရလျှင်)
            if (prices[left] < prices[right]) {
                int currentProfit = prices[right] - prices[left];
                maxProfit = Math.max(maxProfit, currentProfit);
            } else {
                // ရောင်းဈေးက ဝယ်ဈေးထက် ပိုသက်သာသွားပါက ထိုရက်ကို ဝယ်ရက်အသစ်အဖြစ် သတ်မှတ်သည်
                left = right;
            }
            right++; // ရောင်းရက်ကို တစ်ရက်တိုးသည်
        }

        return maxProfit;
    }
}

၃။ Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

ရှင်းလင်းချက်

ပေးထားတဲ့ string ထဲမှာ တူညီတဲ့ စာလုံးထပ်ပြီး ပါဝင်ခြင်းမရှိတဲ့ (No repeating characters) အရှည်ဆုံး substring ရဲ့ အလျားကို ရှာရမှာ ဖြစ်ပါတယ်။

ဒါကို Dynamic Size Sliding Window နဲ့ ဖြေရှင်းနိုင်ပါတယ်။

• left နဲ့ right pointer နှစ်ခု သုံးပြီး ဝင်းဒိုးတစ်ခု ဖန်တီးပါမယ်။
• HashSet (သို့မဟုတ် character status tracking array) တစ်ခု သုံးပြီး လက်ရှိ ဝင်းဒိုးထဲမှာ ရှိနေတဲ့ စာလုံးတွေကို မှတ်သားထားပါမယ်။
• right pointer ကို ညာဘက်သို့ တစ်လုံးချင်း တိုးပြီး ဝင်းဒိုးကို ချဲ့သွားပါမယ်။
  • ဝင်လာတဲ့ စာလုံးက HashSet ထဲမှာ မရှိသေးရင် HashSet ထဲ ထည့်ပြီး ဝင်းဒိုးအကျယ်ကို maxLength = Math.max(maxLength, right - left + 1) ဆိုပြီး တွက်ပါမယ်။
  • ဝင်လာတဲ့ စာလုံးက HashSet ထဲမှာ ရှိပြီးသား ဖြစ်နေရင် (Duplicate တွေ့ရင်)၊ အဲ့ဒီ စာလုံး ထပ်နေတာ မပျောက်မချင်း ဝင်းဒိုးရဲ့ ဘယ်ဘက်ဆုံးက စာလုံးတွေကို HashSet ထဲကနေ ဖယ်ထုတ်ပြီး left pointer ကို ညာဘက်သို့ တိုးရွှေ့ (ဝင်းဒိုးကို ကျဉ်း) ပေးရပါမယ်။

Time Complexity: $O(n)$ - Pointer တစ်ခုချင်းစီဟာ အများဆုံး Array အလျားအတိုင်း တစ်ကြိမ်သာ သွားရလို့ ဖြစ်ပါတယ်။
Space Complexity: $O(\min(m, n))$ - m သည် character set အရွယ်အစားဖြစ်ပြီး၊ window ထဲရှိ unique character များကို သိမ်းထားရန် ဖြစ်သည်။

Java Solution

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> charSet = new HashSet<>();
        int left = 0;
        int maxLength = 0;

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

            // စာလုံးအသစ်သည် လက်ရှိ window ထဲတွင် ရှိပြီးသားဖြစ်နေပါက
            // ၎င်းစာလုံး ပျောက်သွားသည်အထိ left pointer ကို ရွှေ့ပြီး window ကို ကျဉ်းစေသည်
            while (charSet.contains(c)) {
                charSet.remove(s.charAt(left));
                left++;
            }

            // စာလုံးအသစ်အား window ထဲ ထည့်သွင်းသည်
            charSet.add(c);
            // အရှည်ဆုံး အလျားကို တွက်သည်
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

၄။ Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating character, which is 4.
There may exists other ways to achieve this answer too.

ရှင်းလင်းချက်

String တစ်ခု ပေးထားပြီး စာလုံးတွေကို အများဆုံး $k$ ကြိမ်အထိ တခြားစာလုံးတွေနဲ့ အစားထိုးပြောင်းလဲခွင့် ရှိပါတယ်။ အစားထိုးပြီးတဲ့နောက် တူညီတဲ့စာလုံးတွေချည်းပဲ ရှိနေတဲ့ အရှည်ဆုံး Substring အလျားကို မေးတာ ဖြစ်ပါတယ်။

ဒီပုစ္ဆာကို ဖြေရှင်းဖို့ Sliding Window နဲ့ Frequency Map (သို့မဟုတ် character counting array) ကို တွဲသုံးရပါမယ်။

• လက်ရှိ ဝင်းဒိုး [left, right] ထဲမှာ ရှိတဲ့ စာလုံးတွေရဲ့ ကြိမ်နှုန်း (Frequency) ကို သိမ်းထားပါမယ်။
• ဝင်းဒိုးထဲမှာ အများဆုံးပါဝင်တဲ့ စာလုံးရဲ့ ကြိမ်နှုန်းကို maxCount လို့ ခေါ်ပါမယ်။
• ဝင်းဒိုးတစ်ခုလုံးရဲ့ အလျား (right - left + 1) ထဲကနေ maxCount ကို နှုတ်လိုက်ရင် ကျန်တဲ့စာလုံးတွေဟာ ငါတို့ အစားထိုးပြောင်းလဲပစ်ရမယ့် စာလုံးအရေအတွက် ဖြစ်ပါတယ်။
• အဲ့ဒီ ပြောင်းလဲရမယ့် အရေအတွက်ဟာ $k$ ထက် သာလွန်သွားရင် ((right - left + 1) - maxCount > k)၊ ဒီဝင်းဒိုးဟာ မမှန်ကန်တော့တဲ့အတွက် left က စာလုံးရဲ့ ကြိမ်နှုန်းကို လျှော့ပြီး left ကို ညာဘက်သို့ တိုးရွှေ့ရပါမယ်။
• ဝင်းဒိုး မှန်ကန်နေသရွေ့ အရှည်ဆုံးအလျားကို Update လုပ်သွားပါမယ်။

Time Complexity: $O(n)$ - string တစ်ပတ်ပဲ ပတ်ရလို့ဖြစ်ပါတယ်။
Space Complexity: $O(26) = O(1)$ - uppercase English character ၂၆ လုံးအတွက်သာ counting array သိမ်းလို့ ဖြစ်ပါတယ်။

Java Solution

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26]; // English alphabet size
        int maxCount = 0; // လက်ရှိ window ထဲရှိ အများဆုံးပါသော စာလုံး၏ ကြိမ်နှုန်း
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            // ဝင်လာသော စာလုံး၏ ကြိမ်နှုန်းကို တိုးသည်
            count[s.charAt(right) - 'A']++;
            // လက်ရှိ window ထဲရှိ အများဆုံးပါဝင်သော character count ကို update လုပ်သည်
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);

            // ပြောင်းလဲရန် လိုအပ်သော စာလုံးအရေအတွက်သည် k ထက် ကျော်လွန်နေပါက window အား ကျဉ်းစေသည်
            int windowSize = right - left + 1;
            if (windowSize - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

            // မှန်ကန်သော window အရွယ်အစားကို အဖြေအဖြစ် တွက်သည်
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

၅။ Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

ရှင်းလင်းချက်

String s2 ထဲမှာ s1 ရဲ့ Permutation (စာလုံးစီစဉ်မှု ပုံစံကွဲ) တစ်ခုခု Substring အဖြစ် ပါဝင်နေသလား စစ်ဆေးရမှာ ဖြစ်ပါတယ်။ Permutation ဆိုတာ စာလုံးတွေရဲ့ နေရာလွဲနေပေမယ့် ပါဝင်တဲ့ စာလုံးတွေနဲ့ သူတို့ရဲ့ ကြိမ်နှုန်းတွေ တူညီနေတာကို ဆိုလိုပါတယ်။

ဒါကြောင့် ဒါဟာ Fixed-size Sliding Window (ပုံသေအရွယ်အစား ဝင်းဒိုး) ပြဿနာ ဖြစ်ပါတယ်။

• ဝင်းဒိုးရဲ့ အရွယ်အစားဟာ s1.length() အတိုင်း ပုံသေ ဖြစ်ပါတယ်။
• အရင်ဦးဆုံး s1 ထဲမှာ ပါတဲ့ စာလုံးတွေရဲ့ frequency count ကို array မှာ သိမ်းပါမယ်။
• ပြီးရင် s2 ရဲ့ ပထမဆုံး s1.length() အလျားရှိတဲ့ ဝင်းဒိုးရဲ့ character frequency ကိုလည်း တွက်ထားပါမယ်။
• အဲ့ဒီ frequency counts နှစ်ခု တူညီနေရင် true ပြန်ပါမယ်။
• မတူသေးရင် ဝင်းဒိုးကို ညာဘက်သို့ တစ်လုံးချင်း တိုးရွှေ့ပါမယ်။
  • ညာဘက်က စာလုံးအသစ်ကို ပေါင်းထည့်ပြီး၊ ဘယ်ဘက်က ထွက်သွားတဲ့ စာလုံးကို နှုတ်ပစ်ပါမယ်။
  • ခြေလှမ်းတိုင်းမှာ frequencies တူမတူ စစ်ဆေးသွားပါမယ်။

Time Complexity: $O(26 \cdot n) = O(n)$ - iteration တိုင်းမှာ character array ၂၆ လုံး တူမတူ တိုက်စစ်လို့ ဖြစ်ပါတယ်။
Space Complexity: $O(26) = O(1)$

Java Solution

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];

        // s1 ၏ အလျားအတိုင်း ပထမဆုံး window ၏ frequencies ကို တွက်သည်
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }

        // frequencies တူညီပါက permutation တွေ့ရှိပြီ ဖြစ်သည်
        if (Arrays.equals(s1Count, s2Count)) {
            return true;
        }

        // Window အား ညာဘက်သို့ တစ်လုံးချင်း တိုးရွှေ့သွားသည်
        for (int i = s1.length(); i < s2.length(); i++) {
            // ညာဘက်အသစ်ဝင်လာသော စာလုံးအား ပေါင်းသည်
            s2Count[s2.charAt(i) - 'a']++;
            // ဘယ်ဘက်မှ ထွက်သွားသော စာလုံးအား နှုတ်သည်
            s2Count[s2.charAt(i - s1.length()) - 'a']--;

            // frequencies အား တိုက်စစ်သည်
            if (Arrays.equals(s1Count, s2Count)) {
                return true;
            }
        }

        return false;
    }
}

၆။ Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the window of s only has one 'a', return empty string.

ရှင်းလင်းချက်

ဒါကတော့ Sliding Window ရဲ့ အလွန် နာမည်ကြီးပြီး အမေးများတဲ့ Hard အဆင့်ရှိ မေးခွန်း ဖြစ်ပါတယ်။ String s ထဲမှာ String t ရဲ့ စာလုံးအားလုံး (ထပ်နေတာတွေ အပါအဝင်) ပါဝင်တဲ့ အသေးဆုံး/အတိုဆုံး Substring ကို ရှာခိုင်းတာ ဖြစ်ပါတယ်။

ဒါကို Dynamic Size Sliding Window နဲ့ စနစ်တကျ ဖြေရှင်းနိုင်ပါတယ်။

• ပထမဆုံး t ထဲက စာလုံးတွေရဲ့ Frequency Map ကို ဆောက်ပါမယ်။ (ဥပမာ- tMap)
• နောက်ထပ် map တစ်ခု windowMap ထားပြီး လက်ရှိ window ထဲရှိ စာလုံးတွေကို မှတ်ပါမယ်။
• have နဲ့ need ဆိုတဲ့ variable နှစ်ခု သုံးပြီး လိုအပ်တဲ့ စာလုံးအရေအတွက် ပြည့်စုံမှုရှိမရှိကို လျင်မြန်စွာ စစ်ပါမယ်။
  • need = t ထဲက ထူးခြားစာလုံး အရေအတွက် (Unique characters count in t)။
  • have = လက်ရှိ window ထဲမှာ t ရဲ့ character requirements ပြည့်စုံသွားတဲ့ ထူးခြားစာလုံး အရေအတွက်။
• right pointer ကို ညာဘက်ရွှေ့ပြီး window ကို ချဲ့ပါမယ်။ ဝင်လာတဲ့ စာလုံးရဲ့ Frequency က tMap ထဲက တန်ဖိုးနဲ့ ကိုက်ညီသွားရင် have++ လုပ်ပါမယ်။
• have == need ဖြစ်သွားပြီ ဆိုရင် (လိုအပ်တဲ့ စာလုံးတွေ အကုန်ပါသွားပြီဆိုရင်)၊ ဒီ window က မှန်ကန်နေပါပြီ။
  • အဲ့ဒီအခါ အတိုဆုံး window ဖြစ်ဖို့အတွက် ဘယ်ဘက်ဆုံးက စာလုံးတွေကို left pointer တိုးပြီး တစ်လုံးချင်း ဖယ်ထုတ် (window ကို ကျဉ်း) ကြည့်ပါမယ်။
  • ဖယ်ထုတ်လိုက်လို့ စာလုံးလိုအပ်ချက် မပြည့်စုံတော့တဲ့ အခြေအနေ (have < need) ရောက်မှ left ရွှေ့တာကို ရပ်ပြီး right ကို ဆက်ချဲ့ပါမယ်။
  • ပတ်နေစဉ်တစ်လျှောက်လုံးမှာ အတိုဆုံး substring အလျားနဲ့ index ကို မှတ်သားထားပါမယ်။

Time Complexity: $O(m + n)$ - string s ရော t ရောကို တစ်ပတ်စီပဲ ပတ်ရလို့ ဖြစ်ပါတယ်။
Space Complexity: $O(m + n)$ - character counting dictionaries အတွက် ဖြစ်ပါတယ်။

Java Solution

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

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // t ၏ စာလုံးလိုအပ်ချက်များကို မှတ်သားရန် Map
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        // လက်ရှိ window အတွင်းရှိ စာလုံးများကို မှတ်သားရန် Map
        Map<Character, Integer> windowMap = new HashMap<>();

        int left = 0;
        int have = 0;
        int need = tMap.size(); // Unique character count in t

        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;

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

            // t ထဲတွင် လိုအပ်သော စာလုံးဖြစ်ပါက windowMap ထဲ ထည့်သည်
            if (tMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                // လိုအပ်သော အရေအတွက်အတိအကျ ပြည့်သွားပါက 'have' ကို တိုးသည်
                if (windowMap.get(c).equals(tMap.get(c))) {
                    have++;
                }
            }

            // လိုအပ်ချက်များအားလုံး ပြည့်စုံနေပါက window အား တတ်နိုင်သမျှ ကျဉ်းစေသည်
            while (have == need) {
                // အနည်းဆုံး window အလျားကို update လုပ်သည်
                int windowSize = right - left + 1;
                if (windowSize < minLen) {
                    minLen = windowSize;
                    minLeft = left;
                }

                char leftChar = s.charAt(left);
                // ဘယ်ဘက်ဆုံးစာလုံးအား window ထဲမှ ဖယ်ထုတ်သည်
                if (tMap.containsKey(leftChar)) {
                    // ဖယ်ထုတ်လိုက်သဖြင့် လိုအပ်ချက်ထက် နည်းသွားပါက 'have' ကို လျှော့သည်
                    if (windowMap.get(leftChar).equals(tMap.get(leftChar))) {
                        have--;
                    }
                    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                }
                left++;
            }
        }

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

၇။ Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Window တစ်ခုချင်းစီအတွက် အကြီးဆုံးတန်ဖိုးတွေက အောက်ပါအတိုင်း ဖြစ်ပါတယ်။

Example 2:

Input: nums = [1], k = 1
Output: [1]

ရှင်းလင်းချက်

Array တစ်ခုနဲ့ ကိန်းသေ $k$ (Window size) ပေးထားပါတယ်။ ဝင်းဒိုးကို ညာဘက်သို့ တစ်ဆင့်ချင်း ရွှေ့သွားတဲ့အခါ လက်ရှိ ဝင်းဒိုးတစ်ခုချင်းစီထဲမှာ ရှိတဲ့ အကြီးဆုံး တန်ဖိုး (Maximum element) ကို စုစည်းပြီး Array အဖြစ် ပြန်ထုတ်ပေးရမှာ ဖြစ်ပါတယ်။

ပုံမှန်အားဖြင့် ဝင်းဒိုးတစ်ခုချင်းစီထဲက အကြီးဆုံးကို လိုက်ရှာရင် $O(k)$ ကြာပြီး၊ တစ်ပတ်လုံးအတွက် $O(n \cdot k)$ ကြာပါမယ်။ $k$ က ကြီးမားတဲ့အခါ Time Limit Exceeded (TLE) ဖြစ်သွားပါလိမ့်မယ်။

ဒါကို $O(n)$ နဲ့ ဖြေရှင်းဖို့ Monotonic Decreasing Queue (or Deque - Double Ended Queue) နည်းပညာကို သုံးရပါမယ်။ Deque ထဲမှာ Array ရဲ့ တန်ဖိုးတွေအစား သူတို့ရဲ့ index တွေကို သိမ်းဆည်းသွားပါမယ်။

• Deque ထဲက index တွေနဲ့ သက်ဆိုင်တဲ့ တန်ဖိုးတွေကို အမြဲတမ်း ကြီးစဉ်ငယ်လိုက် (Decreasing order) ဖြစ်နေအောင် ထိန်းသိမ်းပါမယ်။
• ဝင်လာတဲ့ nums[right] တန်ဖိုးထက် သေးငယ်တဲ့ Deque ရဲ့ အနောက်ဆုံး (tail) က index တွေကို အကုန် pop ထုတ်ပစ်ပါမယ်။ ဘာဖြစ်လို့လဲဆိုတော့ အခု အသစ်ဝင်လာတဲ့ကောင်က ပိုကြီးပြီး window ထဲမှာ ပိုကြာကြာကျန်မှာဖြစ်လို့၊ သူ့ထက်သေးတဲ့ အရင်ကောင်တွေဟာ ဘယ်တော့မှ အဖြေ (Maximum) ဖြစ်လာစရာ အကြောင်းမရှိတော့လို့ပါ။
• ပြီးရင် လက်ရှိ index right ကို Deque ရဲ့ အနောက်မှာ ထည့်ပါမယ်။
• Deque ရဲ့ အရှေ့ဆုံး (head) က index က လက်ရှိ window ရဲ့ ဘောင်အပြင်ဘက် ရောက်သွားရင် (head_index < right - k + 1)၊ ၎င်းကို အရှေ့ကနေ pop ထုတ်ပစ်ပါမယ်။
• Deque ရဲ့ အရှေ့ဆုံးမှာ ကျန်နေတဲ့ index နဲ့ သက်ဆိုင်တဲ့ တန်ဖိုး nums[deque.peekFirst()] ဟာ လက်ရှိ window ရဲ့ အကြီးဆုံးတန်ဖိုး အမြဲ ဖြစ်နေပါလိမ့်မယ်။

Time Complexity: $O(n)$ - element တစ်ခုချင်းစီဟာ Deque ထဲကို အများဆုံး တစ်ကြိမ်ပဲ ဝင်ပြီး တစ်ကြိမ်ပဲ ထွက်ရလို့ ဖြစ်ပါတယ်။
Space Complexity: $O(k)$ - Deque ရဲ့ အမြင့်ဆုံး size က $k$ ဖြစ်လို့ဖြစ်ပါတယ်။

Java Solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0 || k > nums.length) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0; // result array index

        // Index များကို Decreasing order အတိုင်း သိမ်းမည့် Deque
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Window ၏ အပြင်ဘက် ရောက်သွားသော index အဟောင်းများအား Deque အရှေ့မှ ဖယ်ထုတ်သည်
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // လက်ရှိတန်ဖိုးထက် ငယ်သော Deque အနောက်ဘက်ရှိ index များအားလုံးကို ဖယ်ထုတ်သည်
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // လက်ရှိ index အား Deque ထဲ ထည့်သည်
            deque.offerLast(i);

            // ပထမဆုံး window ပြည့်သွားသည်မှ စတင်၍ အဖြေစသိမ်းသည်
            if (i >= k - 1) {
                result[ri++] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}