You have a line of letter tiles s and a word t. You spell t by crossing out some of the tiles, so that the tiles you keep, read left to right, are exactly t. Two ways are different if they keep a different set of tile positions.
Write count_spellings(s: str, t: str) -> int that returns the number of different ways. The count can be enormous, so return it modulo 1_000_000_007.
count_spellings("banana", "ban") # 3 b + (a at 1) + (n at 2 or 4), or b + (a at 3) + (n at 4)
count_spellings("abcabc", "abc") # 4
count_spellings("aaa", "aa") # 3 keep positions {0,1}, {0,2} or {1,2}
count_spellings("abc", "abcd") # 0 t is longer than s
count_spellings("xyz", "") # 1 cross out everything
count_spellings("a" * 40, "a" * 20) # 846527861 (137846528820 modulo 1_000_000_007)
Constraints:
1 <= len(s) <= 1000,0 <= len(t) <= 1000- both strings contain only lowercase English letters
Listing the ways one by one is hopeless: "a" * 1000 and "a" * 500 alone have about 10^299 of them. Aim for O(len(s) · len(t)) time; O(len(t)) extra memory is a nice bonus.
Show hint
think about the first i tiles and the first j letters of the word. The i-th tile is either crossed out, or, if it matches, it is the one used for the j-th letter; those two cases never overlap, so their counts add up.