Distinct Subsequences

Hard Problem 134 of 151 Java and Python

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 different positions of s.

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3
Why: Any one of the three b's can be left out.

Example 2

Input: s = "babgbag", t = "bag"
Output: 5

Constraints

1 ≤ s.length, t.length ≤ 1000
The answer fits in a 32-bit integer.

Explanation

Let ways(i, j) count how the first i characters of s can form the first j of t. Character s[i - 1] can always be skipped: ways(i - 1, j). If it equals t[j - 1], it can also be used to match it: + ways(i - 1, j - 1).

An empty t can be formed in exactly one way (pick nothing).

Approach 1 · Naive

Plain recursion

Time O(2ⁿ)
Space O(n)

At each character of s, skip it, or use it if it matches the next needed character of t.

count(i, j): 1 if j == t.length; 0 if i == s.length.
Return count(i + 1, j) plus count(i + 1, j + 1) when s[i] == t[j].

Java

class Solution {
    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;
        }
        if (i == s.length()) {
            return 0;
        }
        int ways = count(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            ways += count(s, t, i + 1, j + 1);
        }
        return ways;
    }
}

Python

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        def count(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0
            ways = count(i + 1, j)
            if s[i] == t[j]:
                ways += count(i + 1, j + 1)
            return ways

        return count(0, 0)

Approach 2 · Optimal

DP with one row

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

Keep ways[j] for the prefix of s processed so far. For each new character of s, update j from right to left so each update uses the previous row's value.

ways[0] = 1, the rest 0.
For each character c of s, for j from t.length down to 1: if t[j - 1] == c, ways[j] += ways[j - 1].
Return ways[t.length].

Java

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

Python

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n = len(t)
        ways = [1] + [0] * n
        for c in s:
            for j in range(n, 0, -1):
                if t[j - 1] == c:
                    ways[j] += ways[j - 1]
        return ways[n]

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2ⁿ)	O(n)
Optimal DP with one row	O(m · n)	O(n)

Key takeaways

Iterating j downwards in the one-row version is the same trick as in 0/1 knapsack: it reads the previous row before overwriting it.
Intermediate counts can exceed 32 bits even when the final answer does not; use long in Java.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem