โปรแกรมนับจำนวน subsequence ที่แตกต่างกันใน Python

ได้รับสตริง s ต้องนับจำนวน subsequence ที่แตกต่างกัน (distinct) คำตอบมอดุลลอ 10^9+7

ตัวอย่าง: s="bab" ผลลัพธ์ 6 (subsequences: "a","b","ba","ab","bb","abb")

วิธีแก้ปัญหา

1. dp[i] = จำนวน subsequence ใหม่ที่ลงท้ายด้วย s[i]
2. dp[i] = 1 + sum(dp[0..i-1]) ถ้า s[i] ไม่เคยเจอก่อน มิฉะนั้น sum(dp[last_occurrence..i-1])
3. คืน sum(dp) % MOD

ตัวอย่างโค้ด

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