ซับซีเควลน์ซ้ำไม่ซ้ำกัน II ใน C++

คำอธิบายปัญหา

ให้สตริง S นับจำนวน subsequence ที่ต่างกัน (distinct) ของ S ผลลัพธ์ modulo 10⁹+7

ตัวอย่าง

S = "bab" → Output: 6
Subsequences: "a", "b", "ba", "ab", "bb", "abb"

แนวทางแก้ปัญหา: DP บนตัวอักษรล่าสุด

dp[c] = จำนวน subsequence ที่จบด้วยตัวอักษร c (รวม empty subsequence ที่นำมาต่อ)

เมื่ออ่านตัวอักษร x ใหม่: - subsequence ใหม่ที่จบด้วย x = (total + 1) - dp[x] (total+1 = เพิ่ม x ต่อทุก subsequence เดิม + subsequence "x" เอง) - อัปเดต dp[x] และ total

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

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9+7;

class Solution {
    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; }
    
public:
    int distinctSubseqII(string s) {
        int n = s.size();
        vector<lli> dp(26, 0);
        lli res = 0;
        s = " " + s; // 1-indexed
        
        for(int i=1; i<=n; i++) {
            char x = s[i];
            lli added = sub(add(res, 1), dp[x-'a']);
            dp[x-'a'] = add(dp[x-'a'], added);
            res = add(res, added);
        }
        return res;
    }
};

ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(1) (คงที่ 26 ตัวอักษร)