সমস্যা বিবরণ
একটি স্ট্রিং S দেওয়া থাকলে, তার সব ডISTINCT সাবসিকোয়েন্সের সংখ্যা বের করতে হবে। উত্তর 10^9+7 মডুলো দিয়ে রিটার্ন করুন।
উদাহরণ
S = "bab" → আউটপুট = 6 (সাবসিকোয়েন্স: "a", "b", "ba", "ab", "bb", "abb")
সমাধান পদ্ধতি
- DP দিয়ে প্রতিটি ক্যারেক্টার প্রসেস করা হয়।
- dp[c] = ক্যারেক্টার c দিয়ে শেষ হওয়া সাবসিকোয়েন্সের সংখ্যা।
- প্রতিটি ক্যারেক্টার x-এর জন্য: added = (res + 1) - dp[x], তারপর dp[x] এবং res আপডেট করা হয়।
- মডুলার অ্যারিথমেটিক ফাংশন (add, sub, mul) ব্যবহার করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
lli add(lli a, lli b) { return ((a % MOD) + (b % MOD)) % MOD; }
lli sub(lli a, lli b) { return (((a % MOD) - (b % MOD)) + MOD) % MOD; }
lli mul(lli a, lli b) { return ((a % MOD) * (b % MOD)) % MOD; }
public:
int distinctSubseqII(string s) {
int n = s.size();
vector<lli> dp(26);
int res = 0;
s = " " + s; // 1-based indexing
for (lli i = 1; i <= n; i++) {
char x = s[i];
int added = sub(add(res, 1), dp[x - 'a']);
dp[x - 'a'] = add(dp[x - 'a'], added);
res = add(res, added);
}
return res;
}
};
int main() {
Solution ob;
cout << ob.distinctSubseqII("bab");
return 0;
}ইনপুট ও আউটপুট
ইনপুট: "bab"
আউটপুট: 6
