Strings in a Range Without a Banned Word

Hard

You are given an integer length, two strings low and high of that length, and a string banned. All strings consist of lowercase English letters. Call a string *clean* if: - its length is length; - in dictionary (lexicographic) order it is at least low and at most high; - it does not contain banned as a substring (a contiguous piece). Count the clean strings. The count can be huge, so return it modulo 10⁹ + 7.

Example 1

length=2, low="ax", high="cb", banned="b" → 4

Starting with a: ax, ay, az (3 strings). Everything starting with b contains b. Starting with c, only ca fits, since cb contains b. Total 4.

Example 2

length=4, low="tram", high="trap", banned="ra" → 0

Every string in the range starts with tra and so contains ra. The answer is 0.

Example 3

length=3, low="aaa", high="zzz", banned="qq" → 17525

Constraints

1 ≤ length ≤ 500
len(low) == len(high) == length
low ≤ high
1 ≤ len(banned) ≤ 50
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming String Matching

Similar problems

Peel Off a Repeated Start Hard Tail to the Front Hard Phrase From Word Beginnings, Long Edition Hard Longest Back-to-Back Run Easy Target From Word Beginnings Medium

Input

length=2, low="ax", high="cb", banned="b"

Expected

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