Sticky Keys

Hard

A keyboard has sticky keys: a key press sometimes prints its letter several times in a row instead of once. It never skips letters. The screen now shows the string screen. We know the person meant to type a word of length at least min_len. How many different words could they have meant? The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

screen="aabbb", min_len=3 → 5

The run "aa" could have been 1 or 2 letters and "bbb" 1 to 3: 2 · 3 = 6 options. Only "ab" is shorter than 3, so the answer is 5.

Example 2

screen="xyz", min_len=2 → 1

There are no repeats, so the intended word can only be "xyz".

Example 3

screen="ooo", min_len=4 → 0

The intended word is never longer than what is on screen, and that is only 3 letters.

Constraints

1 ≤ len(screen) ≤ 5 · 10⁵
screen consists of lowercase English letters
1 ≤ min_len ≤ 2000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Prefix Sum

Similar problems

Up and Down Orderings Hard Rugs Over White Tiles Hard Hop Across Safe Tiles Medium Inspecting Three Buildings Medium Pattern With Dot and Star Hard

Input

screen="aabbb", min_len=3

Expected

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