Show problems as
Classic problem #3333HardStringDynamic ProgrammingPrefix Sum

Find the Original Typed String II

Real-world version: Counting the Labels the Stamping Could Have Meant
Tracked in this browser only
Read Find the Original Typed String II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A label was made by pressing one stamp at a time, and a stamp held down too long leaves several copies of its letter in a row. The finished label reads word.

So the label falls into runs of one repeated letter, and a run of L letters could have come from anywhere between 1 and L presses of that stamp.

Return how many different intended labels hold at least k letters. Two intended labels differ when some run came from a different number of presses. Report the count modulo 10^9 + 7.

Examples

Example 1

Input
word = "aabbcc", k = 4
Output
7

The three runs each hold two letters, so eight intended labels are possible, running from three letters up to six. Only the shortest, one press per run, falls below four.

Example 2

Input
word = "aaa", k = 2
Output
2

The single run of three could have come from one, two or three presses, and the last two of those hold at least two letters.

Example 3

Input
word = "ab", k = 2
Output
1

Neither letter repeats, so only one intended label exists, and it holds two letters.

Constraints

  • 1 <= word.length <= 5 * 10^5
  • word holds only lowercase English letters
  • 1 <= k <= 2000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def possible_string_count(word: str, k: int) -> int:
Java
public int possibleStringCount(String word, int k)

More on the same topics