सी ++ में स्ट्रिंग में क्रमपरिवर्तन

मान लीजिए कि हमारे पास दो स्ट्रिंग्स s1 और s2 हैं, यदि s2 में s1 का क्रमपरिवर्तन है, तो हमें सही रिटर्न के लिए एक फंक्शन लिखना होगा। तो हम कह सकते हैं कि पहली स्ट्रिंग के क्रमपरिवर्तन में से एक दूसरी स्ट्रिंग का सबस्ट्रिंग है। इसलिए यदि स्ट्रिंग s1 ="abc", और दूसरी स्ट्रिंग s2 "findcab" है, तो परिणाम सत्य होगा, क्योंकि "abc" का क्रमपरिवर्तन सत्य है। वह है "कैब"।

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

• 26 आकार के दो वेक्टर cnt1 और cnt2 बनाएं
• मेरे लिए 0 से s1 की सीमा में
  • cnt1[s1[i] - 'a'] के मान को 1 से बढ़ाएं
• j :=0 और आवश्यक :=s1 का आकार
• i के लिए 0 से s2 के आकार के बीच
  • x :=s2[i]
  • cnt2[x - 'a'] को 1 से बढ़ाएं
  • अगर cnt1[x - 'a'] और cnt2[x - 'a'] <=cnt[x - 'a'], तो
    • 1 की कमी आवश्यक
  • जबकि j <=i और cnt2[s2[j] - 'a'] - 1>=cnt1[s2[j] - 'a'], करते हैं
    • cnt2[s2[j] - 'a'] को 1 से घटाएं
    • j को 1 से बढ़ाएं
  • यदि i - j + 1 =s1 का आकार और आवश्यक =0, तो सही लौटें
• झूठी वापसी।

उदाहरण(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