পাইথনে ডISTINCT সাবসিকোয়েন্সের সংখ্যা খুঁজে বের করার প্রোগ্রাম

আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর ডISTINCT সাবসিকোয়েন্সের সংখ্যা গণনা করতে হবে। যদি উত্তর অনেক বড় হয় তবে রেজাল্টকে 10^9 + 7 দিয়ে মডুলো করে রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট s = "bab" হলে আউটপুট হবে 6 কারণ ৬টি ভিন্ন সিকোয়েন্স আছে: "a", "b", "ba", "ab", "bb", "abb"।

সমাধানের ধাপসমূহ

dp := s-এর আকারের অ্যারে ০ দিয়ে ফিল করে
m := 10^9 + 7
s-এর প্রতিটি ইন্ডেক্স i এবং আইটেম char এর জন্য:
- ind := s-এ i-তম char-এর ডান পাশ থেকে ইন্ডেক্স
- যদি ind == -1 হয়, তবে dp[i] := 1 + sum(dp[:i]) % m, অন্যথায় dp[i] := sum(dp[ind:i]) % m
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"