Skip to content

115. Distinct Subsequences

Description

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.

Solutions

Solution 1: Dynamic Programming

Thinking

Count subsequences of \(s\) that equal \(t\). Choosing to take or skip each character of \(s\) explodes when both lengths reach \(1000\); naive recursion repeats the same suffix pairs.

The state is how much of \(s\) and \(t\) we have used. \(f[i][j]\) is the number of ways the first \(i\) characters of \(s\) form the first \(j\) of \(t\). When the current characters match, we add the transition that consumes both. The empty \(t\) has exactly one empty subsequence.

We define \(f[i][j]\) as the number of schemes where the first \(i\) characters of string \(s\) form the first \(j\) characters of string \(t\). Initially, \(f[i][0]=1\) for all \(i \in [0,m]\).

When \(i > 0\), we consider the calculation of \(f[i][j]\):

  • When \(s[i-1] \ne t[j-1]\), we cannot select \(s[i-1]\), so \(f[i][j]=f[i-1][j]\);
  • Otherwise, we can select \(s[i-1]\), so \(f[i][j]=f[i-1][j-1]\).

Therefore, we have the following state transition equation:

\[ f[i][j]=\left\{ \begin{aligned} &f[i-1][j], &s[i-1] \ne t[j-1] \\ &f[i-1][j-1]+f[i-1][j], &s[i-1]=t[j-1] \end{aligned} \right. \]

The final answer is \(f[m][n]\), where \(m\) and \(n\) are the lengths of strings \(s\) and \(t\) respectively.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            f[i][0] = 1
        for i, a in enumerate(s, 1):
            for j, b in enumerate(t, 1):
                f[i][j] = f[i - 1][j]
                if a == b:
                    f[i][j] += f[i - 1][j - 1]
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; ++i) {
            f[i][0] = 1;
        }
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                f[i][j] = f[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
        return f[m][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        unsigned long long f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < m + 1; ++i) {
            f[i][0] = 1;
        }
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        f[i][0] = 1
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            f[i][j] = f[i-1][j]
            if s[i-1] == t[j-1] {
                f[i][j] += f[i-1][j-1]
            }
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function numDistinct(s: string, t: string): number {
    const m = s.length;
    const n = t.length;
    const f: number[][] = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; ++i) {
        f[i][0] = 1;
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            f[i][j] = f[i - 1][j];
            if (s[i - 1] === t[j - 1]) {
                f[i][j] += f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
    #[allow(dead_code)]
    pub fn num_distinct(s: String, t: String) -> i32 {
        let n = s.len();
        let m = t.len();
        let mut dp: Vec<Vec<u64>> = vec![vec![0; m + 1]; n + 1];

        // Initialize the dp vector
        for i in 0..=n {
            dp[i][0] = 1;
        }

        // Begin the actual dp process
        for i in 1..=n {
            for j in 1..=m {
                dp[i][j] = if s.as_bytes()[i - 1] == t.as_bytes()[j - 1] {
                    dp[i - 1][j] + dp[i - 1][j - 1]
                } else {
                    dp[i - 1][j]
                };
            }
        }

        dp[n][m] as i32
    }
}

Solution 2: Optimized Dynamic Programming

Thinking

In Solution 1, \(f[i][j]\) depends only on the previous row. After collapsing to one dimension we must update \(j\) from the right, so \(f[j-1]\) is not overwritten too early. Space becomes \(O(|t|)\).

\(f[i][j]\) depends only on the previous row, so the first dimension can be dropped. Update \(j\) from large to small so \(f[j-1]\) is not overwritten. The space complexity becomes \(O(n)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n = len(t)
        f = [1] + [0] * n
        for a in s:
            for j in range(n, 0, -1):
                if a == t[j - 1]:
                    f[j] += f[j - 1]
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int numDistinct(String s, String t) {
        int n = t.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (char a : s.toCharArray()) {
            for (int j = n; j > 0; --j) {
                char b = t.charAt(j - 1);
                if (a == b) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numDistinct(string s, string t) {
        int n = t.size();
        unsigned long long f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (char& a : s) {
            for (int j = n; j; --j) {
                char b = t[j - 1];
                if (a == b) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func numDistinct(s string, t string) int {
    n := len(t)
    f := make([]int, n+1)
    f[0] = 1
    for _, a := range s {
        for j := n; j > 0; j-- {
            if b := t[j-1]; byte(a) == b {
                f[j] += f[j-1]
            }
        }
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function numDistinct(s: string, t: string): number {
    const n = t.length;
    const f: number[] = new Array(n + 1).fill(0);
    f[0] = 1;
    for (const a of s) {
        for (let j = n; j; --j) {
            const b = t[j - 1];
            if (a === b) {
                f[j] += f[j - 1];
            }
        }
    }
    return f[n];
}

Comments