Count Number of Special Subsequences

Count Number of Special Subsequences

What is this problem about?

A "special subsequence" is a sequence of elements from an array that follows the pattern: some number of 0s, followed by some number of 1s, followed by some number of 2s. There must be at least one 0, at least one 1, and at least one 2. You need to return the total number of such subsequences in a given array modulo $10^9 + 7$.

Why is this asked in interviews?

Amazon uses this "Hard" problem to test a candidate's proficiency in Dynamic Programming and state transition. It evaluations whether you can maintain multiple related counters simultaneously and understand how adding a new element affects previous partial solutions. It’s a test of combinatorial logic within a sequence traversal.

Algorithmic pattern used

The pattern is 1D Dynamic Programming with three states.

• dp0: Number of subsequences containing only 0s.
• dp1: Number of subsequences containing 0s followed by 1s.
• dp2: Number of subsequences containing 0s, then 1s, then 2s. When you encounter a new number $x$:
• If $x=0$: A new 0 can start a new sequence or extend all existing dp0 sequences. dp0 = 2 * dp0 + 1.
• If $x=1$: A new 1 can extend all existing dp1 sequences or follow any existing dp0 sequence. dp1 = 2 * dp1 + dp0.
• If $x=2$: A new 2 can extend all existing dp2 sequences or follow any existing dp1 sequence. dp2 = 2 * dp2 + dp1.

Example explanation

Array: [0, 1, 2]

1. $x=0$: dp0 = 2(0) + 1 = 1. (Subsequence: [0])
2. $x=1$: dp1 = 2(0) + 1 = 1. (Subsequence: [0, 1])
3. $x=2$: dp2 = 2(0) + 1 = 1. (Subsequence: [0, 1, 2]) Result: 1. If array was [0, 0, 1, 2]:
4. First 0: dp0 = 1.
5. Second 0: dp0 = 2(1) + 1 = 3. (Subsequences: [0], [0], [0,0])
6. $x=1$: dp1 = 2(0) + 3 = 3. (Subsequences: [0,1], [0,1], [0,0,1])
7. ... and so on.

Common mistakes candidates make

A common mistake is forgetting the "+1" when adding a 0 (the case where the 0 starts a brand-new subsequence). Another is using the wrong order of updates if not using separate variables for the new state. Also, neglecting modulo arithmetic at each step is a frequent error.

Interview preparation tip

For subsequence problems where elements must appear in a specific order (like 0-1-2), think about the "incremental build" approach. Each state represents a stage of completion. This logic is very similar to solving "Number of distinct subsequences" or "Longest increasing subsequence."