परिचय
मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें s के गैर-खाली अद्वितीय सबसीक्वेंसेस (unique subsequences) की संख्या ढूंढनी है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड (mod) करें।
तो, यदि इनपुट s = "xxy" है, तो आउटपुट 5 होगा, क्योंकि पांच सबसीक्वेंसेस हैं: "x", "xx", "xy", "y" और "xxy"।
समाधान दृष्टिकोण
डायनामिक प्रोग्रामिंग का उपयोग करते हुए, हम प्रत्येक कैरेक्टर के लिए अंतिम घटना को ट्रैक करते हैं और डुप्लिकेट सबसीक्वेंसेस से बचने के लिए समायोजित करते हैं।
उदाहरण कोड
#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);
return 0;
}
इनपुट
"xxy"
आउटपुट
5
व्याख्या
"xxy" के अद्वितीय सबसीक्वेंसेस: "x" (पहला), "x" (दूसरा - लेकिन डुप्लिकेट), "xx", "xy", "xxy", "y"। अद्वितीय: "x", "xx", "xy", "xxy", "y" = 5।
निष्कर्ष
यह O(n) समय और O(1) स्पेस (26 आकार की टेबल) समाधान है। प्रत्येक कैरेक्टर के लिए नए सबसीक्वेंसेस की गणना करता है और डुप्लिकेट को घटाता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
