मान लीजिए हमारे पास एक स्ट्रिंग S है, हमें S के विशिष्ट सबसीक्वेंस की संख्या गिननी है। परिणाम बड़ा हो सकता है, इसलिए हम उत्तर को मॉड्यूलो 10^9 + 7 में लौटाएंगे।
उदाहरण के लिए, यदि इनपुट "bab" है, तो आउटपुट 6 होगा, क्योंकि 6 अलग-अलग अनुक्रम हैं: "a", "b", "ba", "ab", "bb", "abb"।
हल करने का दृष्टिकोण
हम अंतिम घटना ट्रैकिंग के साथ डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
मॉड्यूलो अंकगणित के लिए add, sub, mul फ़ंक्शन परिभाषित करें
dp[c] = वर्ण c के साथ समाप्त होने वाले विशिष्ट सबसीक्वेंस की संख्या
res = अब तक के कुल विशिष्ट सबसीक्वेंस
प्रत्येक वर्ण के लिए, नए_जोड़े = res + 1 - dp[c]
dp[c] और res को अपडेट करें
यह डुप्लिकेट को कुशलतापूर्वक संभालता है
उदाहरण
#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;
}
};
int main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
return 0;
}
इनपुट
"bab"
आउटपुट
6