Distinct Subsequences

NeetCode: Distinct Subsequences · LeetCode: 115. Distinct Subsequences · Difficulty: Hard

Given two strings s and t, return the number of distinct subsequences of s that equal t. Subsequences that use different positions of s count separately.

Example

Text

Input:  s = "rabbbit",  t = "rabbit"    Output: 3
Input:  s = "babgbag",  t = "bag"       Output: 5

Brute force: skip or match each character

Walk through s and t together. At position i of s and j of t, s[i] can always be skipped. If s[i] == t[j] it may also match t[j], advancing both. If t is fully matched, that is one subsequence (1); if s runs out first there is none (0). Two branches per character of s means exponential time, and many (i, j) pairs repeat.

Java

class Solution {
    private long count(String s, String t, int i, int j) {
        if (j == t.length()) {
            return 1;
        }
        if (i == s.length()) {
            return 0;
        }
        long ways = count(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            ways += count(s, t, i + 1, j + 1);
        }
        return ways;
    }

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit"));
        System.out.println(sol.numDistinct("babgbag", "bag"));
        System.out.println(sol.numDistinct("abc", "abcd"));
        System.out.println(sol.numDistinct("abc", ""));
    }
}

Output

Time: O(2^m) for |s| = m. Space: O(m).

Better: 2D table

Let dp[i][j] be the number of ways the first i characters of s contain the first j characters of t as a subsequence. An empty t is matched exactly one way (dp[i][0] = 1), and a non-empty t cannot be matched by an empty s (dp[0][j] = 0 for j > 0). For the general cell, s[i-1] can be skipped, giving dp[i-1][j]; if s[i-1] == t[j-1] it can also be used, adding dp[i-1][j-1].

Java

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit"));
        System.out.println(sol.numDistinct("babgbag", "bag"));
        System.out.println(sol.numDistinct("abc", "abcd"));
        System.out.println(sol.numDistinct("abc", ""));
    }
}

Output

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

Optimal: one array, filled right to left

Row i reads only dp[i-1][j] and dp[i-1][j-1]. Use a single array dp[j] and, for each character of s, update j from high to low. Going right to left means dp[j - 1] has not been overwritten yet, so it still holds the previous row's value. Going left to right would double count by reusing the same character of s twice.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit"));
        System.out.println(sol.numDistinct("babgbag", "bag"));
        System.out.println(sol.numDistinct("abc", "abcd"));
        System.out.println(sol.numDistinct("abc", ""));
    }
}

Output

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

The final answer fits in a 32-bit integer, but intermediate counts can be larger, so the tables use long and the result is cast to int at the end.