Problem 31.7 · DP on Strings and SequencesHard

Distinct Subsequences

What it teaches: Counting alignments: on a match, either use the character or skip it.

Practise it on judges as “Distinct Subsequences”.

The problem

Return the number of distinct subsequences of s that equal t.

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3

Constraints

1 ≤ lengths ≤ 1000
The answer fits in an int

Pattern clues in the wording

→ Count ways t appears in s as a subsequence

These clues point to DP on Two Strings: dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int numDistinct(String s, String t) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "rabbbit" t = "rabbit"	3
2	s = "babgbag" t = "bag"	5

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. One-row counting DP · O(n × m)

One-row counting DP

Time O(n × m) Space O(m)

ways[0] = 1 (empty t). For each character of s, update j from m down to 1 so each s character is used once per alignment.

Approach 1

class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length();
        long[] ways = new long[m + 1];
        ways[0] = 1;
        for (int i = 0; i < s.length(); i++)
            for (int j = m; j >= 1; j--)
                if (s.charAt(i) == t.charAt(j - 1)) ways[j] += ways[j - 1];
        return (int) ways[m];
    }
}

Verdict: Downward j avoids overwriting needed values.

Before you submit

Edge cases and common mistakes

Test these inputs

t longer than s (0)
Repeated characters

Mistakes people make

Updating j upwards (one s character fills several t positions).

Interview

Follow-up questions

How is this like 0/1 knapsack?

Command Palette

The problem

Approaches

One-row counting DP

Edge cases and common mistakes

Follow-up questions