Find All Good Strings
Given the strings s1 and s2 of size n and the string evil, return the number of good strings.
A good string:
- Has size
n. - Is alphabetically greater than or equal to
s1. - Is alphabetically smaller than or equal to
s2. - Does not contain the string
evilas a substring.
Since the answer can be a huge number, return it modulo 10^9 + 7.
Example 1
Input
n = 2, s1 = "aa", s2 = "da", evil = "b"Output
51There are 25 good strings starting with 'a', 25 good strings starting with 'c', and one good string starting with 'd'.
Example 2
Input
n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"Output
0All strings in the range start with the prefix "leet", so every such string contains
evil and none are good.Constraints
- s1.length == n
- s2.length == n
- s1 <= s2
- 1 <= n <= 500
- 1 <= evil.length <= 50
- All strings consist of lowercase English letters.