Count Interleavings of Two Strings

Given strings s1, s2, and s3, return the number of distinct interleavings that form s3 while preserving the relative order of characters from s1 and s2. Return the answer modulo 1,000,000,007. Pattern focus: Interleaving strings. This variant counts the number of valid DP paths instead of only checking feasibility.

Input Format

s1 = first string, s2 = second string, s3 = target string

Output Format

number of distinct interleavings that form s3

Constraints

  • 0 <= s1.length, s2.length <= 200
  • s1, s2, s3 contain lowercase English letters.
  • Return the answer modulo 1000000007.

Examples

Example 1:

Input:

s1 = "aa"
s2 = "aa"
s3 = "aaaa"

Output:

6

Explanation:

With s1 = aa and s2 = aa, the number of valid interleavings equals C(4,2) = 6.

Example 2:

Input:

s1 = "abc"
s2 = "def"
s3 = "adbcef"

Output:

1

Explanation:

There is exactly one valid interleaving for this pattern.

Loading...
Count Interleavings of Two Strings - Dp Strings