Two String Formations
HardDynamic Programming · Uber
You are given three lowercase strings p, q, and r. You want to build r one character at a time by taking characters from p and q.
A formation assigns every position k of r to a source string (p or q) and an index in that source holding the character r[k], such that:
- the indices taken from
pstrictly increase askincreases, and the same holds forq(each source is read left to right and no index is used twice), and - at least one position of
ris taken frompand at least one fromq.
Characters of p and q that are not picked are simply skipped. Two formations are different if any position of r is assigned a different source or a different index.
Return the number of formations modulo 10^9 + 7.
Example 1
- Input:
- p = "aab", q = "ab", r = "ab"
- Output:
- 3
- Explanation
- Ignoring the both-sources rule there are 6 ways:
afromp[0],p[1]orq[0], andbfromp[2]orq[1], keeping each source's indices increasing. Two of them use onlypand one uses onlyq, leaving 6 - 2 - 1 = 3.
Example 2
- Input:
- p = "ab", q = "cd", r = "ad"
- Output:
- 1
- Explanation
aexists only inpanddexists only inq, so the single formation isp[0]thenq[1].
Example 3
- Input:
- p = "ab", q = "ab", r = "ab"
- Output:
- 2
- Explanation
- Each character can come from either source, giving 4 ways. The all-
pand all-qways are excluded, so 2 remain:p[0], q[1]andq[0], p[1].
Constraints
0 <= p.length, q.length, r.length <= 50p,q, andrcontain only lowercase English letters