मान लीजिए कि हमारे पास दो स्ट्रिंग्स S और T हैं, हमें S का न्यूनतम सबस्ट्रिंग W ज्ञात करना है, ताकि T, W का परवर्ती हो। यदि S में ऐसी कोई विंडो नहीं है जो T के सभी वर्णों को कवर करती हो, तो खाली स्ट्रिंग लौटाएं। अगर ऐसी कई विंडो हैं, तो हमें सबसे बाईं ओर से शुरू होने वाले इंडेक्स के साथ एक को वापस करना होगा।
इसलिए, यदि इनपुट S ="abcdebdde", T ="bde" जैसा है, तो आउटपुट "bcde" होगा जैसा कि "bdde" से पहले होता है। "deb" कोई छोटी विंडो नहीं है क्योंकि विंडो में T के तत्व क्रम में होने चाहिए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
tidx:=0, tlen:=T का आकार
-
n :=S का आकार
-
मैं:=0, लंबाई:=inf, प्रारंभ:=-1
-
जबकि मैं
-
यदि S[i], T[tidx] के समान है, तो -
-
(tidx को 1 से बढ़ाएं)
-
यदि tidx tlen के समान है, तो -
-
अंत:=मैं + 1
-
(tidx को 1 से घटाएं)
-
जबकि tidx>=0, करें −
-
यदि S[i], T[tidx] के समान है, तो -
-
(tidx को 1 से घटाएं)
-
-
(i 1 से घटाएं)
-
-
(मैं 1 से बढ़ाइए)
-
(tidx को 1 से बढ़ाएं)
-
अगर अंत - i <लंबाई, तो -
-
लंबाई :=अंत - मैं
-
प्रारंभ:=मैं
-
-
-
-
(मैं 1 से बढ़ाइए)
-
-
यदि प्रारंभ -1 के बराबर नहीं है, तो -
-
प्रारंभ करने के लिए मैं:=प्रारंभ, जब मैं <शुरू + लंबाई, अद्यतन (मैं 1 से बढ़ाएँ), करते हैं -
-
रिट:=रिट + एस[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;
}
};
main(){
Solution ob;
cout << (ob.minWindow("abcdebdde", "bde"));
} इनपुट
"abcdebdde", "bde"
आउटपुट
"bcde"