940. Distinct Subsequences II

Problem Overview

Count every distinct non-empty subsequence of s.

Intuition

Count every distinct non-empty subsequence of s. Each new character can extend all existing subsequences and also start a fresh one-letter string. Repeating a letter would double-count old endings, so subtract how many subsequences already ended with that letter.

Algorithm

1Keep ans as total distinct subsequences and endsIn[c] per ending letter.
2For each character c, set add = ans - endsIn[c] + 1.
3Update ans += add and endsIn[c] += add, all modulo 1e9+7.
4Return ans.

Example Walkthrough

Input: s = "aba"

1.After a: one subsequence "a".
2.After b: add "b" and "ab".
3.Second a: extend prior chains but not the first a ending, giving 6 total.

Output: 6

Common Pitfalls

•Subtract endsIn[c] to remove duplicate extensions on repeated letters.
•Keep a running ans instead of summing 26 counts every step.
•Add MOD before modulo when subtracting to avoid negative values.
•Empty subsequence is excluded; the +1 is only the single-letter c.

940.cs

// Approach: Track total distinct subsequences (ans) and count per ending letter.
// At each char, new sequences = ans + 1 minus those already ending with that letter.
// Complexity: O(n) time and O(1) extra space.
public class Solution
{
    public int DistinctSubseqII(string s)
    {
        const int MOD = 1_000_000_007;
        long[] endsIn = new long[26];
        long ans = 0;

        foreach (char c in s)
        {
            int i = c - 'a';
            long add = (ans - endsIn[i] + 1 + MOD) % MOD;
            ans = (ans + add) % MOD;
            endsIn[i] = (endsIn[i] + add) % MOD;
        }

        return (int)ans;
    }
}

Was this solution helpful?