Practice › Dynamic Programming
Distinct Subsequences
Hard · Dynamic Programming · Asked at Google, Amazon, Microsoft, Uber
Count the number of ways to choose a subsequence of s (by index positions) that equals t. Print the count modulo 1,000,000,007.
Input
First line: s. Second line: t. Lowercase letters.
Output
The count modulo 10^9 + 7.
Constraints
- 1 ≤ |s|, |t| ≤ 1000
ways[i][j] = ways for s[0..i) and t[0..j): ways[i−1][j] (skip s[i−1]) plus ways[i−1][j−1] if s[i−1] == t[j−1]. One row suffices if j goes from high to low.
Example 1
Input
rabbbit rabbit
Output
3
Example 2
Input
babgbag bag
Output
5
Hints
- ways[i][j] = number of ways the first i characters of s can form the first j characters of t.
- Either s[i−1] is not used (ways[i−1][j]), or — if s[i−1] == t[j−1] — it matches the last character of t (ways[i−1][j−1]). ways[i][0] = 1.
Approach
Use one array w[j] over the prefix of t, starting with w[0] = 1 (the empty t can be formed in exactly one way). For each character c of s, update j from |t| down to 1: if t[j−1] == c, w[j] += w[j−1]. Going downward keeps w[j−1] at its value from before c was considered, so each character of s is used at most once per subsequence.
Complexity: O(|s| · |t|) time · O(|t|) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
const long long MOD = 1000000007LL;
int m = t.size();
vector<long long> w(m + 1, 0);
w[0] = 1;
for (char c : s)
for (int j = m; j >= 1; j--)
if (t[j - 1] == c) w[j] = (w[j] + w[j - 1]) % MOD;
cout << w[m] << "\n";
return 0;
}Python solution
import sys
s, t = sys.stdin.read().split()[:2]
MOD = 10**9 + 7
m = len(t)
w = [0] * (m + 1)
w[0] = 1
for c in s:
for j in range(m, 0, -1):
if t[j - 1] == c:
w[j] = (w[j] + w[j - 1]) % MOD
print(w[m])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), t = sc.next();
long MOD = 1000000007L;
int m = t.length();
long[] w = new long[m + 1];
w[0] = 1;
for (char c : s.toCharArray())
for (int j = m; j >= 1; j--)
if (t.charAt(j - 1) == c) w[j] = (w[j] + w[j - 1]) % MOD;
System.out.println(w[m]);
}
}