C++ में न्यूनतम विंडो सबस्ट्रिंग

मान लीजिए हमारे पास एक स्ट्रिंग S और T है। हमें S में न्यूनतम विंडो ढूंढनी है जिसमें T के सभी कैरेक्टर्स हों। यदि इनपुट "ABHDAXCVBAGTXATYCB" और T = "ABC" है, तो परिणाम "CVBA" होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक मैप m बनाएं
• x की आवृत्ति को m में स्टोर करें
• length := s का आकार, left := 0, right := 0, ansLeft := 0, ansRight := 0
• counter := x का आकार, flag := false, ans := खाली स्ट्रिंग
• जब तक right < s का आकार:
  • c := s[right]
  • यदि c, m में मौजूद है:
    • यदि m[c] > 0, तो counter को 1 घटाएं
    • m[c] को 1 घटाएं
  • जब तक 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 वापस करें
• अन्यथा ansLeft से ansRight तक के कैरेक्टर्स को ans में जोड़ें
• 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