Loading...
Loading...
Loading...
For a poster, Kabir cuts letters out of an old banner. The banner text is a string of lowercase letters. He wants to spell his club name by picking letters from the banner from left to right, keeping their order.
Two ways are different if they use a different set of positions on the banner. Print the number of ways to spell the club name, modulo 10^9 + 7. If it cannot be spelled, print 0.
Example 1
Input
banana ban
Output
3
The b is at position 0. The pairs of a then n are positions (1, 2), (1, 4) and (3, 4).
Example 2
Input
abab ab
Output
3
The pairs of positions are (0, 1), (0, 3) and (2, 3).
Try the problem first. Open one hint at a time.
Look at the last banner letter. Either it is not used, or it is used as the last letter of the club name.
It can be used only when it equals the last letter of the club name. Then the rest of the name must come from the earlier banner letters.
Let ways[i][j] be the count for the first i banner letters and the first j letters of the name. An empty name can always be spelled in exactly one way.
Fill the table row by row and take the remainder modulo 10^9 + 7 after each addition.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor