इस समस्या में, हमें एक स्ट्रिंग str और एक पूर्णांक pow दिया गया है। हमारा कार्य दिए गए पावर वाला एक सब-स्ट्रिंग ढूंढना है।
हमें वह सबस्ट्रिंग लौटानी होगी जिसका पावर pow के बराबर हो।
स्ट्रिंग का पावर उसके वर्णों के पावर का योग है।
वर्ण का पावर: a → 1, b → 2, c → 3, ...
उदाहरण से समझते हैं:
इनपुट: स्ट्रिंग = "programming" पावर = 49 आउटपुट: 'pro'
व्याख्या:
मैट्रिक्स का पावर: pro, पावर(p) = 16 पावर(r) = 18 पावर(o) = 15 कुल = 16 + 18 + 15 = 49
समाधान दृष्टिकोण
समस्या का एक सरल समाधान नेस्टेड लूप का उपयोग करना है। हम स्ट्रिंग के माध्यम से लूप करेंगे और एक आंतरिक लूप का उपयोग करके सबस्ट्रिंग ढूंढेंगे। प्रत्येक सबस्ट्रिंग के लिए, हम पावर की गणना करेंगे। और फिर जांचेंगे कि क्या यह 'pow' के बराबर है, यदि हां तो true लौटाएं, अन्यथा false लौटाएं।
समस्या को हल करने का एक कुशल दृष्टिकोण मैप का उपयोग करके पावर संग्रहीत करना है। हम सबस्ट्रिंग का पावर गणना करेंगे और इसे मैप पर संग्रहीत करेंगे। जांचें कि क्या मैप में कोई मान मौजूद है जो पावर को आवश्यक पावर के बराबर बना सकता है। यदि हां, तो true लौटाएं। जब स्ट्रिंग के सभी वर्ण ट्रैवर्स हो जाएं और पावर से मेल खाने वाला कोई मान न मिले तो false लौटाएं।
एल्गोरिथम
चरण 1 - स्ट्रिंग को ट्रैवर्स करें और पावर (currPow) ज्ञात करें।
चरण 2 - जांचें कि मान (currPow - pow) मैप में मौजूद है या नहीं।
चरण 2.1 - यदि हां, तो प्रिंट करें -> सबस्ट्रिंग।
चरण 3 - currPow का मान मैप में डालें।
चरण 4 - यदि स्ट्रिंग के सभी वर्ण ट्रैवर्स हो जाते हैं, तो प्रिंट करें -> 'संभव नहीं'।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; void findSubStringWithPower(string str, int power) { int i; unordered_map<int , int > powerSS; int currPower = 0; int N = str.length(); for (i = 0; i < N; i++) { currPower = currPower + (str[i] - 'a' + 1); if (currPower == power) { cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power; return; } if (powerSS.find(currPower - power) != powerSS.end()) { cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1); cout<<" has power "<<power; return; } powerSS[currPower] = i; } cout<<"No substring found!"; } int main() { string str = "programming"; int power = 49; findSubStringWithPower(str, power); return 0; } आउटपुट
Substring : pro has power 49
