मान लीजिए हमारे पास दो स्ट्रिंग्स s1 और s2 हैं, हमें एक फ़ंक्शन लिखना है जो true लौटाए यदि s2 में s1 का क्रमचय (permutation) है। तो हम कह सकते हैं कि पहली स्ट्रिंग के क्रमचयों में से एक दूसरी स्ट्रिंग का उपस्ट्रिंग (substring) है। इसलिए यदि स्ट्रिंग s1 = "abc" है, और दूसरी स्ट्रिंग s2 "findcab" है, तो परिणाम true होगा, क्योंकि "abc" का क्रमचय सत्य है। वह "cab" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- आकार 26 के दो वेक्टर cnt1 और cnt2 बनाएं
- i को 0 से s1 तक की रेंज में
- cnt1[s1[i] - 'a'] के मान को 1 से बढ़ाएं
- j := 0 और required := s1 का आकार
- i को 0 से s2 के आकार तक की रेंज में
- x := s2[i]
- cnt2[x - 'a'] को 1 से बढ़ाएं
- यदि cnt1[x - 'a'] और cnt2[x - 'a'] <= cnt[x - 'a'], तो
- required को 1 से घटाएं
- जब तक j <= i और cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a'], करें
- cnt2[s2[j] - 'a'] को 1 से घटाएं
- j को 1 से बढ़ाएं
- यदि i - j + 1 = s1 का आकार और required = 0, तो true लौटाएं
- false लौटाएं।
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: bool checkInclusion(string s1, string s2) { vector <int> cnt1(26), cnt2(26); for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++; int j = 0; int required = s1.size(); for(int i = 0; i < s2.size(); i++){ char x = s2[i]; cnt2[x - 'a']++; if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--; while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){ cnt2[s2[j] - 'a']--; j++; } if(i - j + 1 == s1.size() && required == 0){ return true; } } return false; } }; main(){ Solution ob; cout << (ob.checkInclusion("abc", "findcab")); }इनपुट
"abc" "findcab"
आउटपुट
1
