C++ में मिनिमम विंडो सबसीक्वेंस

मान लीजिए हमारे पास दो स्ट्रिंग्स S और T हैं, हमें S का न्यूनतम सबस्ट्रिंग W ढूंढना है, ताकि T, W का सबसीक्वेंस हो। यदि S में ऐसा कोई विंडो नहीं है जो T के सभी कैरेक्टर्स को कवर करे, तो खाली स्ट्रिंग लौटाएं। यदि ऐसी कई विंडोज हैं, तो हमें बाएं-मोस्ट स्टार्टिंग इंडेक्स वाली को लौटाना होगा।

तो, यदि इनपुट S = "abcdebdde", T = "bde" है, तो आउटपुट "bcde" होगा क्योंकि यह "bdde" से पहले होता है। "deb" एक छोटी विंडो नहीं है क्योंकि विंडो में T के एलिमेंट्स क्रम में होने चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• tidx := 0, tlen := T का आकार

• n := S का आकार

• i := 0, लेंथ := इन्फ, स्टार्ट := -1

• जब i < n, करें:

  • यदि S[i], T[tidx] के समान है, तो:

    • (tidx को 1 से बढ़ाएं)

    • यदि tidx, tlen के समान है, तो:

      • एंड := i + 1

      • (tidx को 1 से घटाएं)

      • जब tidx >= 0, करें:

        • यदि S[i], T[tidx] के समान है, तो:

          • (tidx को 1 से घटाएं)

        • (i को 1 से घटाएं)

      • (i को 1 से बढ़ाएं)

      • (tidx को 1 से बढ़ाएं)

      • यदि एंड - i < लेंथ, तो:

        • लेंथ := एंड - i

        • स्टार्ट := i

  • (i को 1 से बढ़ाएं)

• यदि स्टार्ट -1 के बराबर नहीं है, तो:

  • i := स्टार्ट से शुरू करें, जब i < स्टार्ट + लेंथ, अपडेट करें (i को 1 से बढ़ाएं), करें:

    • रेट := रेट + S[i]

• रेट लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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

class Solution {
public:
    string minWindow(string S, string T) {
        int tidx = 0;
        int tlen = T.size();
        int n = S.size();
        int i = 0;
        int length = INT_MAX;
        int start = -1;
        string ret;
        while (i < n) {
            if (S[i] == T[tidx]) {
                tidx++;
                if (tidx == tlen) {
                    int end = i + 1;
                    tidx--;
                    while (tidx >= 0) {
                        if (S[i] == T[tidx]) {
                            tidx--;
                        }
                        i--;
                    }
                    i++;
                    tidx++;
                    if (end - i < length) {
                        length = end - i;
                        start = i;
                    }
                }
            }
            i++;
        }
        if (start != -1)
            for (int i = start; i < start + length; i++)
                ret += S[i];
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.minWindow("abcdebdde", "bde"));
}

इनपुट

"abcdebdde", "bde"

आउटपुट

"bcde"