Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. ways[i][j] = number of ways the first i characters of s can form the first j characters of t.
  2. 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]);
    }
}

Solve Distinct Subsequences online · All practice problems