Topics › Dynamic Programming › DP on Strings

Distinct subsequences

Hard TUF ID 306 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given two strings s and t, count how many different ways you can delete characters from s (keeping the order of what is left) so that the result equals t. Two ways are different when they keep a different set of positions of s, even if the resulting strings look the same. Because the count grows very fast, return it modulo 10^9 + 7.

Constraints: 1 ≤ |s|, |t| ≤ 1000, lowercase English letters. The Java methods also accept empty strings. LeetCode 115 asks for the exact count and promises it fits in a 32-bit integer; in that case the modulo never changes the answer, so the same code solves both versions.

Example 1

s = "rabbbit", t = "rabbit"
answer = 3          // keep any two of the three b's: ra[bb]bit, ra[b]b[b]it, rab[bb]it

Example 2

s = "babgbag", t = "bag"
answer = 5          // positions (0,1,3), (0,1,6), (0,5,6), (2,5,6), (4,5,6)

The recurrence

Write f(i, j) for the number of ways to form the prefix t[0..j) from the prefix s[0..i). Using prefix lengths instead of last indices makes both base cases about empty prefixes and lets the table use row 0 and column 0 for them:

• f(i, 0) = 1 for every i. The empty target is formed in exactly one way: keep nothing.
• f(0, j) = 0 for j > 0. An empty source cannot produce a non-empty target.

Now look at the last character of the source, s[i - 1]. Every way of forming t[0..j) from s[0..i) falls into exactly one of two groups:

1. It does not keep s[i - 1]. Then it is a way of forming t[0..j) from s[0..i - 1). There are f(i - 1, j) of these.
2. It keeps s[i - 1]. Since s[i - 1] is the last kept position, it must become the last character of the target, so this is only possible when s[i - 1] == t[j - 1]. The remaining kept positions form t[0..j - 1) from s[0..i - 1), giving f(i - 1, j - 1) ways.

The two groups do not overlap (a way either keeps position i - 1 or it does not) and together they cover every way, so the counts simply add:

f(i, j) = f(i - 1, j) + (s[i - 1] == t[j - 1] ? f(i - 1, j - 1) : 0)

This is the counting version of “take it or skip it”. Notice the asymmetry with LCS: here we only ever shrink s on its own, never t, because every character of t must be used.

Approach 1: Recursion

Intuition. Translate the recurrence into code. The base case for j is checked first, so f(0, 0) correctly returns 1: an empty source does form the empty target once.

Algorithm.

1. If j == 0, return 1. If i == 0, return 0.
2. Let skip = f(i - 1, j).
3. If the last characters differ, return skip.
4. Otherwise return (f(i - 1, j - 1) + skip) mod 10^9 + 7.

static int recursive(String s, String t) {
    return solve(s.length(), t.length(), s, t);
}

/** Ways to form t[0..j) from characters of s[0..i). */
static int solve(int i, int j, String s, String t) {
    if (j == 0) return 1;                                    // all of t is matched: one way (pick nothing more)
    if (i == 0) return 0;                                    // t still has characters but s is used up
    int skip = solve(i - 1, j, s, t);                        // s[i - 1] is not used for t[j - 1]
    if (s.charAt(i - 1) != t.charAt(j - 1)) return skip;
    int use = solve(i - 1, j - 1, s, t);                     // s[i - 1] is matched to t[j - 1]
    return (use + skip) % MOD;
}

Complexity. Time O(2^n) in the worst case: every call decreases i by one and branches at most twice, so the depth is at most n and the call tree has at most 2^n leaves. Strings with many repeated letters come close to that bound. Space O(n) for the recursion stack.

Approach 2: Memoization

Intuition. The arguments are just (i, j), so there are only (n + 1)(m + 1) distinct subproblems, yet the recursion reaches the same one along many paths. In the all-a example, “skip then use” and “use then skip” both lead to f(i - 2, j - 1). Store each result in dp[i][j] the first time it is computed. The sentinel is -1 because 0 is a perfectly common answer.

Algorithm.

1. Create dp[n + 1][m + 1] filled with -1.
2. Run the same recursion, returning dp[i][j] immediately when it is known and storing every computed value before returning it.

static int memoization(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(n, m, s, t, dp);
}

static int memo(int i, int j, String s, String t, int[][] dp) {
    if (j == 0) return 1;
    if (i == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int skip = memo(i - 1, j, s, t, dp);
    if (s.charAt(i - 1) != t.charAt(j - 1)) return dp[i][j] = skip;
    int use = memo(i - 1, j - 1, s, t, dp);
    return dp[i][j] = (use + skip) % MOD;
}

Complexity. Time O(n · m): each state is computed once and does constant work besides its two lookups. Space O(n · m) for the table plus O(n) recursion depth. With n = 1000 the depth is 1000 frames, which the default JVM stack handles.

Approach 3: Tabulation

Intuition. Row i only reads row i - 1, so filling rows from top to bottom guarantees every dependency is ready. The base cases become the edges of the table: column 0 is all ones, and the rest of row 0 is zero, which a fresh Java array already is.

Algorithm.

1. Create dp[n + 1][m + 1] and set dp[i][0] = 1 for every i.
2. For i = 1 .. n and j = 1 .. m: start from dp[i - 1][j] and add dp[i - 1][j - 1] when s[i - 1] == t[j - 1].
3. Return dp[n][m].

static int tabulation(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = 1;               // the empty t is formed exactly once
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
        }
    }
    return dp[n][m];
}

Dry run on Example 1 (s = "rabbbit" down the side, t = "rabbit" across):

Bold cells are matches where the upper-left value contributes new ways. Take the row of the third b and the column of the second b, which counts ways to form rabb from rabbb. Its value 3 is the cell above (1 way to form rabb from rabb, ignoring the new b) plus the cell above-left (2 ways to form rab from rabb, each extended by the new b). Every other cell copies the value above it, because a non-matching source character can only be skipped.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Row i reads only the cell directly above and the cell above-left. Keep a single array ways, where before processing source character i it holds row i - 1. Updating ways[j] in place is ways[j] = ways[j] + ways[j - 1], but ways[j - 1] must still be the old row’s value. Walking j from right to left guarantees that: when we touch ways[j], the entries to its left have not been updated in this row yet. When characters differ, the new value equals the old one, so there is nothing to write.

This is the same trick as 0/1 knapsack in one dimension. Each source character may be used at most once per way, and the right-to-left order prevents it from being used twice.

Algorithm.

1. ways = new int[m + 1], ways[0] = 1.
2. For each i = 1 .. n, for j = m down to 1: if s[i - 1] == t[j - 1], set ways[j] = (ways[j] + ways[j - 1]) mod 10^9 + 7.
3. Return ways[m].

static int spaceOptimized(String s, String t) {
    int n = s.length(), m = t.length();
    int[] ways = new int[m + 1];
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) ways[j] = (ways[j] + ways[j - 1]) % MOD;
        }
    }
    return ways[m];
}

Dry run on Example 2 (s = "babgbag", t = "bag"), showing ways after each source character:

The answer is ways[3] = 5.

Complexity. Time O(n · m), space O(m).

Edge cases and pitfalls

• Empty target. f(i, 0) = 1, including ("", ""). Check j == 0 before i == 0 in the recursion, or ("", "") returns 0.
• Target longer than source. ("aaa", "aaaa") must be 0. The recurrence handles it naturally, because j can never reach 0 before i does.
• Direction of the 1D loop. Going left to right lets one source character be used for two target positions. With s = "a", t = "aa", a left-to-right loop sets ways[1] = 1 and then reads that new value to make ways[2] = 1, but the true answer is 0.
• Overflow. The real count can be astronomically large: s = "a" × 200, t = "a" × 100 gives C(200, 100), about 9 × 10^58. Taking the modulo after every addition keeps each value below 10^9 + 7. The sum of two such values is at most about 2 × 10^9, which still fits in an int, so no long is needed. The Java tests compare this case against a Pascal’s triangle computation of the binomial.
• “Distinct” means distinct positions. ("aaaaa", "aa") is C(5, 2) = 10, even though all ten choices spell the same string.
• Memo sentinel. Use -1, not 0, because 0 is a valid count.
• Testing. Besides the fixed cases, 300 seeded random pairs over {a, b} are checked across all four methods.

Related problems

• Longest common subsequence uses the same prefix-length table, but maximises a length instead of counting.
• Edit distance is another two-string DP where each cell looks at its top, left and diagonal neighbours.
• Wildcard matching asks whether a pattern can produce a string, a yes/no cousin of “how many ways”.
• Count subsets with sum K counts take-or-skip choices with the same right-to-left 1D update.