Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

विभिन्न सबसीक्वेंस II C++ में

मान लीजिए हमारे पास एक स्ट्रिंग 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
  1. - C++ में सभी बढ़ते हुए सबसीक्वेंस गिनें

    इस ट्यूटोरियल में, हम बढ़ते हुए अनुक्रमों की संख्या खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें 0 से 9 तक के अंकों वाला एक ऐरे प्रदान किया जाएगा। हमारा कार्य ऐरे में मौजूद सभी अनुक्रमों को गिनना है जैसे कि अगला एलिमेंट पिछले एलिमेंट से बड़ा हो।उदाहरण#include<bits/stdc++.h> using na

  1. - C++ में स्ट्रिंग के सभी उपअनुक्रम प्रिंट करें

    इस समस्या में, हमें एक स्ट्रिंग दी गई है और हमें स्ट्रिंग के सभी उपअनुक्रम प्रिंट करने हैं। उत्पन्न उपस्ट्रिंग स्ट्रिंग के तत्वों को हटाकर बनाई जाती है लेकिन क्रम वही रहता है (अर्थात क्रम बदला नहीं जा सकता)। विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं - इनपुट: xyz आउटपुट: x,y,z,xy,yz,xz,xyz

  1. - C++ में सॉर्टेड एरे में निरपेक्ष विशिष्ट गिनती

    एक एरे समान डेटा प्रकार के तत्वों का एक संग्रह है। एक सॉर्टेड एरे एक एरे है जिसमें तत्व आरोही या अवरोही क्रम के अनुक्रम में संग्रहीत होते हैं। विशिष्ट गिनती उन तत्वों की संख्या है जो समान नहीं हैं। निरपेक्ष विशिष्ट गिनती तत्वों के निरपेक्ष मान की विशिष्ट गिनती है यानी चिह्न के बिना मान (अनसाइन्ड मा