Skills101
← All coding problems

Distinct Subsequences

mediumDynamic Programming II+20 XPTime limit 2s

Count how many times the word t appears in the text s as a subsequence: choose positions in s (in increasing order) whose letters spell t. Two ways are different if they use a different set of positions. Print the count modulo 1 000 000 007.

Input: two lines: s, then t.

Output: the number of ways modulo 10⁹ + 7.

Constraints: 1 ≤ length of s, t ≤ 1000; lowercase letters.

Example: t = bag appears in s = babgbag in 5 ways.

Think about it: ways[i][j] = ways to form the first j letters of t from the first i letters of s. The letter s[i] is either skipped (ways[i−1][j]) or, when it equals t[j], used (+ ways[i−1][j−1]). One row is enough if you update j from right to left.

Sample input 1

babgbag
bag

Sample output 1

5

Sample input 2

rabbbit
rabbit

Sample output 2

3

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.