Minimum Window Substring ใน C++

สมมติว่าเรามีสตริง S และ T เราต้องหา window ขนาดเล็กที่สุดใน S ที่มีตัวอักษรทั้งหมดใน T เช่นถ้าอินพุตคือ "ABHDAXCVBAGTXATYCB" และ T = "ABC" ผลลัพธ์จะเป็น "CVBA"

ขั้นตอนการแก้ปัญหา

• สร้างแมป m
• เก็บความถี่ของ x ลงใน m
• length := ขนาดของ s, left := 0, right := 0, ansLeft := 0 และ ansRight := 0
• counter := ขนาดของ x, flag := false, ans := สตริงว่าง
• while right < ขนาดของ s
  • c := s[right]
  • ถ้า c อยู่ใน m
    • ถ้า m[c] > 0 ลด counter ลง 1
    • ลด m[c] ลง 1
  • while counter = 0 และ left <= right
    • ถ้า right – left + 1 <= length
      • length := right – left + 1
      • flag := true
      • ansLeft := left, ansRight := right
    • ถ้า left = right หยุดลูป
    • c := s[left]
    • ถ้า c อยู่ใน m เพิ่ม m[c] ขึ้น 1
    • ถ้า m[c] > 0 เพิ่ม counter ขึ้น 1
    • เพิ่ม left ขึ้น 1
  • เพิ่ม right ขึ้น 1
• ถ้า flag เป็น false คืนค่า ans
• มิฉะนั้น for i ในช่วง ansLeft ถึง ansRight เพิ่ม ans ด้วย s[i]
• คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string minWindow(string s, string x) {
        map<char, int> m;
        for(int i = 0; i < x.size(); i++) m[x[i]]++;
        int length = s.size();
        int left = 0, right = 0, ansLeft = 0, ansRight = 0;
        int counter = x.size();
        bool flag = false;
        string ans = "";
        while(right < s.size()){
            char c = s[right];
            if(m.find(c) != m.end()){
                if(m[c] > 0) counter--;
                m[c]--;
            }
            while(counter == 0 && left <= right){
                if(right - left + 1 <= length){
                    length = right - left + 1;
                    flag = true;
                    ansLeft = left;
                    ansRight = right;
                }
                if(left == right) break;
                c = s[left];
                if(m.find(c) != m.end()){
                    m[c]++;
                    if(m[c] > 0) counter++;
                }
                left++;
            }
            right++;
        }
        if(!flag) return ans;
        else
            for(int i = ansLeft; i <= ansRight; i++) ans += s[i];
        return ans;
    }
};

int main(){
    Solution ob;
    cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

อินพุต

"ABHDAXCVBAGTXATYCB" "ABC"

เอาต์พุต

CVBA