मान लीजिए हमारे पास एक स्ट्रिंग s और एक नॉन-खाली स्ट्रिंग p है, हमें s में p के सभी एनाग्राम के स्टार्ट इंडेक्स ढूंढने हैं। स्ट्रिंग्स में केवल लोअरकेस लेटर्स होते हैं और दोनों स्ट्रिंग्स s और p की लंबाई 20 और 100 से अधिक नहीं होगी। उदाहरण के लिए, यदि s: "cbaebabacd" p: "abc", तो आउटपुट [0, 6] होगा, इंडेक्स 0 पर, यह "cba" है, और दूसरा "bac" है, ये "abc" के एनाग्राम हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक मैप m परिभाषित करें, n := s का आकार, लेफ्ट := 0, राइट := 0, काउंटर := p का आकार सेट करें
- ans नामक एक ऐरे परिभाषित करें
- p में कैरेक्टर्स की फ्रीक्वेंसी को मैप m में स्टोर करें
- राइट := 0 से n - 1 तक
- यदि m में s[राइट] है और m[s[राइट]] नॉन-जीरो है, तो m[s[राइट]] को 1 से घटाएं, काउंटर को 1 से घटाएं और यदि काउंटर = 0 है, तो लेफ्ट को ans में डालें
- अन्यथा
- जब तक लेफ्ट < राइट,
- यदि s[लेफ्ट] m में मौजूद नहीं है, तो काउंटर को 1 से बढ़ाएं, और m[s[लेफ्ट]] को 1 से बढ़ाएं
- लेफ्ट को 1 से बढ़ाएं
- यदि m में s[राइट] है और m[s[राइट]] नॉन-जीरो है, तो राइट को 1 से घटाएं, और लूप से बाहर आएं
- यदि m में s[लेफ्ट] नहीं है, तो लेफ्ट := राइट + 1 सेट करें
- जब तक लेफ्ट < राइट,
- ans लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> findAnagrams(string s, string p) { map <char, int> m; int n = s.size(); int left = 0, right = 0; int counter = p.size(); vector <int> ans; for(int i = 0; i < p.size(); i++) m[p[i]]++; for(int right = 0; right < n; right++){ if(m.find(s[right]) != m.end() && m[s[right]]){ m[s[right]]--; counter--; if(counter == 0)ans.push_back(left); } else { while(left<right){ if(m.find(s[left]) != m.end()) { counter++; m[s[left]]++; } left++; if(m.find(s[right]) != m.end() && m[s[right]]){ right--; break; } } if(m.find(s[left])==m.end())left = right + 1; } } return ans; } }; main(){ Solution ob; print_vector(ob.findAnagrams("cbaebabacd", "abc")) ; }इनपुट
"cbaebabacd" "abc"
आउटपुट
[0, 6, ]
