मान लीजिए हमारे पास एक स्ट्रिंग एस है, हमें एस के अलग-अलग बाद की संख्या की गणना करनी है। परिणाम बड़ा हो सकता है, इसलिए हम उत्तर मॉड्यूल 10^9 + 7. वापस कर देंगे।
इसलिए, यदि इनपुट "बाब" जैसा है, तो आउटपुट 6 होगा, क्योंकि 6 अलग-अलग क्रम हैं, ये "ए", "बी, "बीए", "एबी", "बीबी", "एबीबी" हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एमओडी) + (बी मॉड एमओडी)) मॉड एमओडी
-
एक फ़ंक्शन उप () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी (((एक मॉड एमओडी) - (बी मॉड एमओडी)) + एमओडी) मॉड एमओडी
-
फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एमओडी) * (बी मॉड एमओडी)) मॉड एमओडी
-
मुख्य विधि से, तो निम्नलिखित -
-
n :=s का आकार
-
26 के आकार की dp सरणी परिभाषित करें
-
रेस :=0
-
s :=s से पहले अंतरिक्ष को संयोजित करें
-
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
-
एक्स:=एस [i]
-
जोड़ा गया:=उप (जोड़ें (रेस, 1), डीपी [एक्स - 'ए'])
-
dp[x - 'a'] =add(dp[x - 'a'], जोड़ा गया)
-
रेस:=जोड़ें (रेस, जोड़ा गया)
-
-
रिटर्न रेस
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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