মান লইয়া আমাদের একটি স্ট্রিং s আছে, আমাদের বের করতে হবে s-এর নন-এমপ্টি ইউনিক সাবসিকোয়েন্সের সংখ্যা। যদি উত্তর বড় হয় তবে 10^9 + 7 দিয়ে মড করুন।
তবে, যদি ইনপুট হয় s = "xxy", তবে আউটপুট হবে 5, কারণ পাঁচটি সাবসিকোয়েন্স আছে: "x", "xx", "xy", "y" এবং "xxy"।
এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:
- m := 10^9 + 7
- n := s-এর সাইজ
- সাইজ ২৬-এর একটি table অ্যারে ডিফাইন করুন
- res := 0
- i = 1 থেকে n পর্যন্ত:
- c := s[i-1] - 'a' এর ASCII
- curr := (res + 1 - table[c] + m) mod m
- res := (res + curr) mod m
- table[c] := (table[c] + curr) mod m
- res রিটার্ন করুন
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
#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
