{x}
blog image

Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

 

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag

 

Constraints:

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

115. Distinct Subsequences

Problem Description

Given two strings s and t, find the number of distinct subsequences of s that are equal to t. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Solution Approach: Dynamic Programming

This problem can be efficiently solved using dynamic programming. We create a 2D array dp where dp[i][j] represents the number of distinct subsequences of the first i characters of s that are equal to the first j characters of t.

Base Cases:

  • dp[i][0] = 1 for all i, because there's always one way to form an empty subsequence.
  • dp[0][j] = 0 for all j > 0, because you can't form a non-empty subsequence from an empty string.

Recursive Relation:

  • If s[i-1] == t[j-1], it means the last characters match. We can either include the last character of s in the subsequence (adding to the count from dp[i-1][j-1]) or exclude it (keeping the count from dp[i-1][j]). Therefore, dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
  • If s[i-1] != t[j-1], we cannot include the last character of s, so dp[i][j] = dp[i-1][j].

Final Result:

The final answer is dp[m][n], where m is the length of s and n is the length of t.

Time and Space Complexity

  • Time Complexity: O(m*n), where m and n are the lengths of strings s and t respectively. We iterate through the dp array of size (m+1) * (n+1).
  • Space Complexity: O(m*n) for the dp array. However, this can be optimized to O(n) by using only one row of the dp array (as shown in Solution 2).

Code Implementation (Python, Java, C++, Go, TypeScript, Rust)

Solution 1 (using O(m*n) space):

Python:

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

Java:

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

C++:

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

Go:

func numDistinct(s string, t string) int {
	m, n := len(s), len(t)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = 1
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[m][n]
}

TypeScript:

function numDistinct(s: string, t: string): number {
    const m = s.length;
    const n = t.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
};

Rust:

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let m = s.len();
        let n = t.len();
        let mut dp = vec![vec![0; n + 1]; m + 1];
        for i in 0..=m {
            dp[i][0] = 1;
        }
        for i in 1..=m {
            for j in 1..=n {
                if s.chars().nth(i - 1).unwrap() == t.chars().nth(j - 1).unwrap() {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        dp[m][n] as i32
    }
}

Solution 2 (optimized space complexity to O(n)):

This solution uses only one row of the dp array, reducing space complexity. The logic remains the same.

Python:

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

(Java, C++, Go, TypeScript examples are similar and follow the same space-optimized approach, iterating through the dp array from the end to avoid overwriting values needed in the current iteration).

This detailed explanation and code examples should help you understand the solution to this problem effectively. Remember to choose the solution that best fits your needs regarding space optimization. For larger inputs, Solution 2's space efficiency becomes a significant advantage.