Distinct Subsequences

Moderate

0/80

Contributed by

104 upvotes

Asked in companies

Problem statement

A Subsequence of a string is the string that is obtained by deleting 0 or more letters from the string and keeping the rest of the letters in the same order.

We are given two strings, 'str' and 'sub'.

Find the number of subsequences of 'str' which are equal to 'sub'.

Since the answer can be very large, print it modulo 10 ^ 9 + 7.

Example :

Input: 'str' = “brootgroot” and 'sub' = “brt”

Output: 3

Explanation: The following subsequences formed by characters at given indices (0-based) of 'str' are equal to 'sub' :

str[0] = ‘b’, str[1] = ‘r’, str[4] = ‘t’

str[0] = ‘b’, str[1] = ‘r’, str[9] = ‘t’

str[0] = ‘b’, str[6] = ‘r’, str[9] = ‘t’

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains the string 'str', denoting the first string of the problem statement.

The second line contains the string 'sub', denoting the second string of the problem statement.

Output Format:

Print the number of subsequences of 'str' which are equal to 'sub' (modulo 1000000007).

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Sample Input 1 :

brootgroot
brt

Sample Output 1 :

Explanation For Sample Input 1 :

The following subsequences formed by characters at given indices (0-based) of 'str' are equal to 'sub' :

str[0] = ‘b’, str[1] = ‘r’, str[4] = ‘t’

str[0] = ‘b’, str[1] = ‘r’, str[9] = ‘t’

str[0] = ‘b’, str[6] = ‘r’, str[9] = ‘t’

Sample Input 2 :

dingdingdingding
ing

Sample Output 2 :

Sample Input 3:

aaaaa
a

Sample Output 3:

Expected time complexity :

The expected time complexity is O(|str| * |sub|).

Constraints:

1 <= |str| <= 1000
1 <= |sub| <= 1000

Where |str| represents the length of the string 'str', and |sub| represents the length of the string 'sub'.

Time Limit: 1 sec.

Console