Number of Unique Good Subsequences

Number of Unique Good Subsequences

What is this problem about?

The Number of Unique Good Subsequences problem gives you a binary string. A "good subsequence" is either "0" or starts with '1' (no leading zeros except for the single subsequence "0"). Count the number of distinct good subsequences modulo 10^9+7. This hard coding problem uses DP tracking the number of distinct subsequences ending with '0' or '1'.

Why is this asked in interviews?

Oracle and Google ask this hard string DP problem because it requires careful reasoning about what makes subsequences distinct and when to handle leading zeros. The string and dynamic programming interview pattern is demonstrated with a clean two-state DP.

Algorithmic pattern used

Two-state DP. Maintain end0 = number of distinct good subsequences ending with '0', and end1 = number ending with '1'. For each character c:

• If c = '0': end0 = end0 + end1. (Append '0' to all ending-with-1 subsequences, plus previous end0 values overridden by the new unique ones — actually end0 = end0 + end1 gives new count since all end1 subsequences now also have an ending-0 version.)
• If c = '1': end1 = end0 + end1 + 1. (+1 for the single character "1"). Final answer: end0 + end1 + has_zero (add 1 if '0' exists in string for the "0" subsequence).

Example explanation

s = "1101". Process:

• '1': end1 = 0+0+1 = 1. (Subseq: "1").
• '1': end1 = 0+1+1 = 2. (Subseq: "1","11").
• '0': end0 = 0+2 = 2. (Subseq: "10","110").
• '1': end1 = 2+2+1 = 5. (Subseq: "1","11","101","1101","111"... wait, need careful counting). Answer = end0 + end1 + (1 if '0' in s) = 2+5+1 = 8.

Common mistakes candidates make

• Including leading-zero subsequences (must only count "0" itself, not "00" or "01..").
• Off-by-one in the DP transitions.
• Not adding the standalone "0" subsequence separately (it's a special case).
• Forgetting modular arithmetic at each transition.

Interview preparation tip

Distinct subsequence counting problems require careful state design to avoid double-counting. The two-state DP (end0, end1) naturally avoids duplicates because each state represents the count of unique subsequences by their last character. The key insight: appending a character merges all valid predecessors into new unique endings. Practice distinct subsequence problems: "count distinct subsequences," "count distinct binary subsequences," "count palindromic subsequences."