Distinct Subsequences

HardDynamic Programming · String DP🧩 String DP LeetCode #115 ↗Updated Oct 30, 2026

Problem

Given two strings s and t, count in how many ways you can delete characters from s (possibly none) so that what remains is exactly t. Two ways differ if they keep a different set of positions of s. The answer is guaranteed to fit in a 32-bit signed integer.

Inputs = "rabbbit", t = "rabbit"Output3 (drop any one of the three b's)

Inputs = "babgbag", t = "bag"Output5

1 ≤ |s|, |t| ≤ 1000 · lowercase/uppercase English letters

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Scan s one character at a time. If s[i] == t[j], every way of building t[0..j-1] so far can now be extended by this character, so ways[j+1] += ways[j]. Update j from right to left so each character of s is used at most once per subsequence.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceSkip-or-Match Recursion

Time O(2ⁿ)Space O(n)

At position i of s and j of t, we may always skip s[i]; if the characters are equal we may also match and advance both. Reaching the end of t counts as one way.

Java

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

private int count(String s, String t, int i, int j) {
    if (j == t.length()) return 1;                      // all of t matched
    if (s.length() - i < t.length() - j) return 0;      // not enough characters left
    int ways = count(s, t, i + 1, j);                   // skip s[i]
    if (s.charAt(i) == t.charAt(j)) {
        ways += count(s, t, i + 1, j + 1);              // use s[i] for t[j]
    }
    return ways;
}

Mirrors the definition exactly, but the same (i, j) pairs are re-explored.

Better2-D Tabulation on Prefixes

Time O(n · m)Space O(n · m)

Let dp[i][j] be the number of ways the first j letters of t appear in the first i letters of s. The empty t appears once in anything; otherwise dp[i][j] = dp[i-1][j] + (s[i-1]==t[j-1] ? dp[i-1][j-1] : 0).

Java

public int numDistinct(String s, String t) {
    int n = s.length(), m = t.length();
    long[][] dp = new long[n + 1][m + 1];   // long: inner cells can exceed int range
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];                          // ignore s[i-1]
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];                 // let s[i-1] play t[j-1]
            }
        }
    }
    return (int) dp[n][m];
}

Each state is solved once, but the full n × m table is kept.

Optimal1-D DP, Right-to-Left Update

Time O(n · m)Space O(m)

Row i of the table only reads row i-1, and only at columns j and j-1. Keep one array and walk j from m down to 1: ways[j-1] is still the previous row's value when we add it.

Java

public int numDistinct(String s, String t) {
    int m = t.length();
    long[] ways = new long[m + 1];   // ways[j] = ways to form t[0..j) so far
    ways[0] = 1;                     // the empty prefix is always formable once
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        for (int j = m; j >= 1; j--) {               // right-to-left: use ch at most once
            if (t.charAt(j - 1) == ch) ways[j] += ways[j - 1];
        }
    }
    return (int) ways[m];
}

Dry runs = "rabbbit", t = "rabbit"

j index updated changed

start
1

0

0

0

s=babgbag, t=bag
i=0 b
1

1
j
0

0

ways[1] += 1
i=1 a
1

1

1
j
0

ways[2] += 1
i=2,3
1

2

1

1

b: [1]=2, g: [3]=1
i=4,5
1

3

4

1

b: [1]=3, a: [2]=4
i=6 g
1

3

4

5
j
ways[3] = 5 ✔

Same time, memory proportional to |t| only — the interview target.

Pro tip

If you loop j left-to-right, one character of s can be counted twice (e.g. s="a", t="aa" would wrongly give 1).

At a glance

Level	Approach	Time	Space
Brute Force	Skip-or-Match Recursion	`O(2ⁿ)`	`O(n)`
Better	2-D Tabulation on Prefixes	`O(n · m)`	`O(n · m)`
Optimal	1-D DP, Right-to-Left Update	`O(n · m)`	`O(m)`

Common pitfalls

Forgetting the base case ways[0] = 1 — every count stays 0.
Left-to-right inner loop in the 1-D version — reuses the same character of s.
Plain int cells — intermediate counts can exceed 2³¹ even though the final answer fits.

Interview tips

Clarify that we count position sets, not distinct resulting strings (they are all equal to t).
Start from the skip/match recursion, then name the state (i, j) to justify memoization.
Draw the 2-D table for “babgbag”/“bag” and show it collapses into one row.

Pattern

Two-string DP → a state (i, j) over prefixes of both strings with skip/match transitions, compressible to one row.

My notes saved in this browser