ধরুন আমাদের একটি স্ট্রিং S আছে, আমাদের S এর স্বতন্ত্র অনুগামী সংখ্যা গণনা করতে হবে। ফলাফল বড় হতে পারে, তাই আমরা উত্তর মডিউল 10^9 + 7 ফেরত দেব।
সুতরাং, যদি ইনপুটটি "bab" এর মত হয়, তাহলে আউটপুট হবে 6, যেহেতু 6টি ভিন্ন ক্রম রয়েছে, এইগুলি হল "a", "b, "ba", "ab", "bb", "abb"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
(a mod MOD) + (b mod MOD)) mod MOD
ফেরত দিন -
একটি ফাংশন সাব() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
ফেরত (((a mod MOD) - (b mod MOD)) + MOD) mod MOD
-
একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
(a mod MOD) * (b mod MOD)) mod MOD
ফেরত দিন -
প্রধান পদ্ধতি থেকে, তাই নিম্নলিখিত -
-
n :=s
এর আকার -
26 আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন
-
res :=0
-
s :=s
এর আগে স্পেস সংযুক্ত করুন -
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
x :=s[i]
-
যোগ করা হয়েছে :=সাব(add(res, 1), dp[x - 'a'])
-
dp[x - 'a'] =add(dp[x - 'a'], যোগ করা হয়েছে)
-
res :=add(res, add)
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
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;
}
int distinctSubseqII(string s) {
int n = s.size();
vector <lli> dp(26);
int res = 0;
s = " " + s;
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;
}
};
main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
} ইনপুট
"bab"
আউটপুট
6
