นับจำนวน subsequence ที่ไม่ซ้ำกันของสตริงใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะนับ จำนวน subsequence ที่ไม่ซ้ำกัน (unique non-empty subsequences) ของสตริง s ผลลัพธ์ mod 10⁹+7

ตัวอย่าง

Input: "xxy"
Output: 5
Subsequences: "x", "xx", "xy", "y", "xxy"

อัลกอริทึม: Dynamic Programming

ให้ dp[i] = จำนวน unique subsequences ของ prefix สูงสุด i
เมื่อเพิ่มตัวอักษร c ใหม่:

• Subsequences ใหม่ = subsequences เก่าทุกอัน + c, และ c เอง
• แต่ต้องลบ subsequences ที่จบด้วย c แล้ว (เพราะจะซ้ำ)
• ใช้ array last[c] เก็บจำนวน subsequences ที่จบด้วย c ล่าสุด

สูตรเวียนเกิด

curr = (res + 1 - last[c] + MOD) % MOD
res = (res + curr) % MOD
last[c] = (last[c] + curr) % MOD

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

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int solve(string s) {
    int n = s.size();
    vector last(26, 0);  // last[c] = จำนวน subseq ที่จบด้วย c
    long long res = 0;
    
    for (int i = 1; i <= n; ++i) {
        int c = s[i - 1] - 'a';
        int curr = (res + 1 - last[c] + MOD) % MOD;
        res = (res + curr) % MOD;
        last[c] = (last[c] + curr) % MOD;
    }
    return res;
}

int main() {
    string s = "xxy";
    cout << solve(s);
    return 0;
}

ผลลัพธ์

5

คำอธิบาย "xxy"

• i=1, 'x': curr=1, res=1, last['x']=1 → {"x"}
• i=2, 'x': curr=1, res=2, last['x']=2 → {"x", "xx"}
• i=3, 'y': curr=3, res=5, last['y']=3 → เพิ่ม "y", "xy", "xxy"

สรุป

DP O(n) นับ unique subsequences โดยติดตาม last occurrence ของแต่ละตัวอักษร หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ