এই সমস্যায়, আমাদের একটি স্ট্রিং str এবং একটি ইন্টিজার pow দেওয়া আছে। আমাদের কাজ হল দেওয়া পাওয়ার যুক্ত একটি সাব-স্ট্রিং খুঁজে বের করা।
আমাদের সেই সাবস্ট্রিংটি রিটার্ন করতে হবে যার পাওয়ার pow-এর সমান।
স্ট্রিংর পাওয়ার হল তার ক্যারেক্টারগুলোর পাওয়ারের যোগফল।
ক্যারেক্টারের পাওয়ার: a → 1, b → 2, c → 3, ...
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : string = "programming" power = 49 আউটপুট : 'pro'
ব্যাখ্যা:
pro-এর পাওয়ার: p=16, r=18, o=15 মোট = 16 + 18 + 15 = 49
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা স্ট্রিংতে লুপ চালাব এবং ইনার লুপ দিয়ে সাবস্ট্রিং খুঁজে বের করব। প্রতিটি সাবস্ট্রিংয়ের পাওয়ার ক্যালকুলেট করব। এবং চেক করব যে সেটি 'pow'-এর সমান কি না, সমান হলে true রিটার্ন করব, অন্যথায় false।
একটি দক্ষ পদ্ধতি হল ম্যাপ ব্যবহার করে পাওয়ার সংরক্ষণ করা। আমরা সাবস্ট্রিংর পাওয়ার ক্যালকুলেট করব এবং ম্যাপে সংরক্ষণ করব। চেক করব যে ম্যাপে এমন কোনো মান আছে কি যা যোগ করলে পাওয়ারটি প্রয়োজনীয় পাওয়ারের সমান হয়। যদি হয়, true রিটার্ন করব। সব ক্যারেক্টার ট্রাভার্স হলে এবং পাওয়ার মিলে না থাকলে false রিটার্ন করব।
অ্যালগরিদম
স্টেপ ১ − স্ট্রিং ট্রাভার্স করুন এবং পাওয়ার বের করুন (currPow)।
স্টেপ ২ − চেক করুন মানটি, (currPow - pow) ম্যাপে আছে কি না।
স্টেপ ২.১ − যদি থাকে, সাবস্ট্রিং প্রিন্ট করুন।
স্টেপ ৩ − currPow মানটি ম্যাপে ইনসার্ট করুন।
স্টেপ ৪ − যদি স্ট্রিংর সব ক্যারেক্টার ট্রাভার্স হয়ে যায়, 'not possible' প্রিন্ট করুন।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#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
