150NeetCode 150

118.Distinct Subsequences

Hard2-D Dynamic Programming · 8/11
LeetCode #115Video

Problem

Given two strings s and t, return the number of distinct subsequences of s that equal t.

Two subsequences are different if they use a different set of indices in s, even if the resulting strings look the same. The answer is guaranteed to fit in a 32-bit signed integer.

Examples

Input:  s = "rabbbit", t = "rabbit"
Output: 3
Explanation: s has three 'b's; drop exactly one of them:
             ra_bbit, rab_bit, rabb_it  (the underscore marks the dropped 'b')
Input:  s = "babgbag", t = "bag"
Output: 5
Explanation: Index choices (b, a, g):
             (0,1,3), (0,1,6), (0,5,6), (2,5,6), (4,5,6)
Input:  s = "abc", t = "abcd"
Output: 0
Explanation: t is longer than s.

Constraints

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

💡 Key Insight

Walk through s one character at a time while trying to match t. At s[i] you can always skip it; if s[i] == t[j] you may also use it to match t[j]. The two options produce disjoint sets of index choices, so their counts simply add: ways(i, j) = ways(i + 1, j) + (s[i] == t[j] ? ways(i + 1, j + 1) : 0). Matching all of t counts as 1; running out of s first counts as 0. The table compresses to one row if j is iterated in the right direction.

Recursion (Brute Force)

TimeO(2^m)SpaceO(m)

Intuition

ways(i, j) = number of ways s[i..] contains t[j..] as a subsequence. Apply skip/use at each character.

Algorithm

  1. ways(i, j):
    • If j == t.length(), return 1 (all of t matched).
    • If i == s.length(), return 0.
    • res = ways(i + 1, j) (skip s[i]).
    • If s[i] == t[j]: res += ways(i + 1, j + 1) (use s[i]).
  2. Return ways(0, 0).

Visualization

flowchart TD
    A["ways(0,0)<br/>s='abb' t='ab'"] -->|"use a"| B["ways(1,1)<br/>'bb' vs 'b'"]
    A -->|"skip a"| C["ways(1,0)<br/>'bb' vs 'ab' → 0"]
    B -->|"use b"| D["ways(2,2) = 1"]
    B -->|"skip b"| E["ways(2,1)<br/>'b' vs 'b'"]
    E -->|"use b"| F["ways(3,2) = 1"]
    E -->|"skip b"| G["ways(3,1) = 0"]
    D --> H["total = 1 + 1 = 2"]
    F --> H

Code

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

    private int ways(String s, String t, int i, int j) {
        if (j == t.length()) {
            return 1; // matched all of t
        }
        if (i == s.length()) {
            return 0; // ran out of s
        }
        int res = ways(s, t, i + 1, j); // skip s[i]
        if (s.charAt(i) == t.charAt(j)) {
            res += ways(s, t, i + 1, j + 1); // use s[i] for t[j]
        }
        return res;
    }
}

Complexity

  • Time: O(2^m) — each character of s may branch twice.
  • Space: O(m) — recursion depth.

Complexity Comparison

Approach Time Space
Recursion (Brute Force) O(2^m) O(m)
Top-Down Memoization O(m · n) O(m · n)
Bottom-Up 2-D Tabulation O(m · n) O(m · n)
Space-Optimized 1-D DP O(m · n) O(n)

Common Pitfalls

  • Iterating j left-to-right in the 1-D version — dp[j-1] would already include the current character, so one s character could match two t characters.
  • Base cases in the wrong order: check j == t.length() before i == s.length(), since matching all of t at the very end of s is a success.
  • Forgetting dp[i][0] = 1 for every row (not just dp[0][0]).
  • Some LeetCode tests produce intermediate counts beyond int range while the final answer fits; Java int wrap-around keeps the final sum correct, but switching to long alone does not prevent the overflow in other languages.
  • Adding an early exit if (m < n) return 0; is a nice optimization, but make sure it doesn't skip the t == "" case (answer 1).