ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর অ-খালি অনন্য অনুক্রমের সংখ্যা খুঁজে বের করতে হবে। যদি উত্তরটি খুব বড় হয় তবে ফলাফলটি 10^9 + 7 দ্বারা পরিবর্তন করুন।
সুতরাং, যদি ইনপুটটি s ="xxy" এর মতো হয়, তাহলে আউটপুট হবে 5, কারণ পাঁচটি অনুসৃতি রয়েছে:"x", "xx", "xy", "y" এবং "xxy"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m :=10^9 + 7
-
n :=s
এর আকার -
26 আকারের একটি অ্যারে টেবিল সংজ্ঞায়িত করুন
-
res :=0
-
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট (i 1 দ্বারা বাড়ান), do−
-
c :=s[i − 1] − 'a'
এর ASCII -
curr :=(res + 1 − table[c] + m) mod m
-
res :=(res + curr) mod m
-
টেবিল[c] :=(টেবিল[c] + curr) mod m
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
int n = s.size();
vector<int> table(26);
long long res = 0;
for (int i = 1; i <= n; ++i) {
int c = s[i − 1] − 'a';
int curr = (res + 1 − table[c] + m) % m;
res = (res + curr) % m;
table[c] = (table[c] + curr) % m;
}
return res;
}
int main(){
string s = "xxy";
cout << solve(s);
} ইনপুট
"xxy"
আউটপুট
5
