पायथन में विशिष्ट सबसीक्वेंस की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें स्ट्रिंग s के विशिष्ट सबसीक्वेंस की संख्या गिननी है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 मॉड्यूलो वापस करें।

उदाहरण के लिए, यदि इनपुट s = "bab" है, तो आउटपुट 6 होगा क्योंकि 6 अलग-अलग अनुक्रम हैं, ये हैं "a", "b", "ba", "ab", "bb", "abb"।

हल करने के चरण

1. dp := s के आकार का ऐरे और 0 से भरें
2. m := 10^9 + 7
3. s में प्रत्येक इंडेक्स i और आइटम char के लिए:
   • ind := s.rfind(char, 0, i) से i-वें कैरेक्टर का दायां इंडेक्स
   • dp[i] := 1 + (sum(dp[:i]) % m) यदि ind == -1 अन्यथा (sum(dp[ind:i]) % m)
4. sum(dp) % m वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(s):
    dp, m = [0] * len(s), 10**9 + 7
    for i, char in enumerate(s):
        ind = s.rfind(char, 0, i)
        dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
    return sum(dp) % m

s = "bab"
print(solve(s))

इनपुट

"bab"

आउटपुट

6