1154HardStringDynamic ProgrammingPrefix Sum

Counting the Labels the Stamping Could Have Meant

Tracked in this browser only

Trains the technique from

LeetCode 3333Find the Original Typed String II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def possible_string_count(word: str, k: int) -> int:

Java

public int possibleStringCount(String word, int k)

The intended approach

Time O(n) to find the runs, plus O(m * k) for the sweep when the runs number fewer than k.Space O(k) for the counts per length.

Each run is chosen independently, so the intended labels number the run lengths multiplied together, and the intended label's length is the chosen counts added up. Counting only those of length at least `k` is awkward head-on, but its opposite is easy to bound: an intended label shorter than `k` holds fewer than `k` letters in total, and there are at most `2000` of those lengths to track. So take the whole product and subtract the intended labels that fall short. Sweep the runs carrying, for each total length below `k`, how many choices so far reach it. Bringing in a run of `L` letters extends every recorded length by anything from `1` to `L`, which is a sliding window over the previous counts, done in one step each with running sums rather than a loop per choice. One shortcut matters for the size limits. Every run contributes at least one letter, so if the runs already number `k` or more, nothing can fall short and the whole product is the answer outright. That leaves the sweep to run only when the runs number fewer than `k`, keeping it to the runs times `k` rather than the whole label times `k`.

Pythonentry point: possible_string_count

def possible_string_count(word, k):
    mod = 1000000007
    n = len(word)
    runs = []
    i = 0
    while i < n:
        j = i
        while j < n and word[j] == word[i]:
            j += 1
        runs.append(j - i)
        i = j
    whole = 1
    for length in runs:
        whole = whole * length % mod
    if len(runs) >= k:
        return whole
    dp = [0] * k
    dp[0] = 1
    for length in runs:
        pref = [0] * (k + 1)
        for s in range(k):
            pref[s + 1] = (pref[s] + dp[s]) % mod
        step = [0] * k
        for s in range(1, k):
            lo = s - length
            if lo < 0:
                lo = 0
            step[s] = (pref[s] - pref[lo]) % mod
        dp = step
    short = 0
    for s in range(k):
        short = (short + dp[s]) % mod
    return (whole - short) % mod

The obvious version

Spell out every choice: pick a press count for each run from one up to its length, take every combination, add the counts and see whether the total reaches `k`. Costs the run lengths multiplied together.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_possible_string_count(word, k):
    from itertools import product
    mod = 1000000007
    n = len(word)
    runs = []
    i = 0
    while i < n:
        j = i
        while j < n and word[j] == word[i]:
            j += 1
        runs.append(j - i)
        i = j
    choices = []
    for length in runs:
        choices.append(range(1, length + 1))
    total = 0
    for combo in product(*choices):
        span = 0
        for value in combo:
            span += value
        if span >= k:
            total += 1
    return total % mod

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in