Ways to Cross Out

Hard

You are given strings source and pattern. You may cross out any characters of source so that the remaining ones, in their original order, spell exactly pattern. Count the number of ways to do it. Two ways differ if the sets of positions of source left uncrossed are different. The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

source="bananas", pattern="ans" → 3

The a can come from position 1 or 3, the n from position 2 or 4 to its right, and the s is the last letter: the pairs (1,2), (1,4), (3,4) give 3 ways.

Example 2

source="aaaa", pattern="aa" → 6

Any two of the four letters: 4·3/2 = 6 ways.

Example 3

source="abc", pattern="cab" → 0

Constraints

1 ≤ len(source), len(pattern) ≤ 1000
Both strings consist of English letters (lowercase and uppercase)
The answer does not exceed 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Fewest Cuts Into Palindromes Hard

Input

source="bananas", pattern="ans"

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.