Problem statement

Alice tried to type a string on her keyboard, but she may have held some keys down too long, so a character could appear one or more times in a row where she meant to type it once.

You are given word, what appeared on the screen, and a positive integer k. It is known that the string Alice intended to type had length at least k.

Return the number of different strings Alice might have intended. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input: word = "aabbccdd", k = 7
Output: 5
Explanation: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd" and "abbccdd".

Example 2

Input: word = "aabbccdd", k = 8
Output: 1
Explanation: Only the screen text itself is long enough.

Example 3

Input: word = "aaabbb", k = 3
Output: 8
Explanation: Each of the two runs keeps 1, 2 or 3 characters (9 ways); only "ab" is shorter than 3.

Constraints

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

Hints for Find the Original Typed String II

1. Hint 1

   Split word into runs of equal characters. An intended string keeps between 1 and len characters of every run, independently.

2. Hint 2

   The total number of candidates is the product of the run lengths. It is easier to subtract the candidates that are too short (total length < k).

3. Hint 3

   If there are at least k runs, nothing is too short. Otherwise count the ways to reach each total s < k with a DP over runs, where each run adds 1..len — a sliding-window sum over the previous row.

How to solve Find the Original Typed String II

Every run of equal characters on the screen came from one intended character typed one or more times, so a candidate is a choice of kept length 1..len for each run. Count all choices (a product) and subtract the ones whose total length is below k, which only involve sums below 2000.

Approach

1. Compute the run lengths g_1, ..., g_m and total = Π g_i mod 10^9 + 7.
2. If m >= k, every candidate has length at least m >= k: return total.
3. Otherwise let dp[s] (for s < k) be the number of ways the runs processed so far keep exactly s characters; start with dp[0] = 1.
4. For each run g, new[s] = dp[s - 1] + dp[s - 2] + ... + dp[s - g] (indices >= 0), computed with prefix sums.
5. Return (total - Σ dp[s]) mod 10^9 + 7, adding the modulus back if the difference is negative.

Why it works

Different choices of kept lengths give different strings (the run structure of the intended string is the same as the screen's), so counting choices counts strings. Only totals below k must be excluded, and those are bounded by k, so the DP never needs more than k states per run.

Complexity

• Time — O(n + m · k)
• Space — O(k)

Pitfalls

• Without the m >= k shortcut the DP is O(m · k) for up to 5 · 10^5 runs — the shortcut caps m below k.
• The subtraction is modular: take (total - bad + MOD) % MOD.
• k may exceed the length of word, in which case the answer is 0.

Reference solution

Python

def possibleStringCount(word: str, k: int) -> int:
    MOD = 10**9 + 7
    groups = []
    i = 0
    while i < len(word):
        j = i
        while j < len(word) and word[j] == word[i]:
            j += 1
        groups.append(j - i)
        i = j
    total = 1
    for g in groups:
        total = total * g % MOD
    if len(groups) >= k:
        return total
    dp = [0] * k
    dp[0] = 1
    for g in groups:
        pre = [0] * (k + 1)
        for s in range(k):
            pre[s + 1] = (pre[s] + dp[s]) % MOD
        nd = [0] * k
        for s in range(k):
            nd[s] = (pre[s] - pre[max(0, s - g)]) % MOD
        dp = nd
    return (total - sum(dp)) % MOD

Java

public static int possibleStringCount(String word, int k) {
    final long MOD = 1000000007L;
    List<Integer> groups = new ArrayList<>();
    for (int i = 0; i < word.length();) {
        int j = i;
        while (j < word.length() && word.charAt(j) == word.charAt(i)) j++;
        groups.add(j - i);
        i = j;
    }
    long total = 1;
    for (int g : groups) total = total * g % MOD;
    if (groups.size() >= k) return (int) total;
    long[] dp = new long[k];
    dp[0] = 1;
    for (int g : groups) {
        long[] pre = new long[k + 1];
        for (int s = 0; s < k; s++) pre[s + 1] = (pre[s] + dp[s]) % MOD;
        long[] nd = new long[k];
        for (int s = 0; s < k; s++) nd[s] = (pre[s] - pre[Math.max(0, s - g)] + MOD) % MOD;
        dp = nd;
    }
    long bad = 0;
    for (long x : dp) bad = (bad + x) % MOD;
    return (int) ((total - bad + MOD) % MOD);
}

C++

int possibleStringCount(string word, int k) {
    const long long MOD = 1000000007LL;
    vector<int> groups;
    for (size_t i = 0; i < word.size();) {
        size_t j = i;
        while (j < word.size() && word[j] == word[i]) j++;
        groups.push_back((int) (j - i));
        i = j;
    }
    long long total = 1;
    for (int g : groups) total = total * g % MOD;
    if ((int) groups.size() >= k) return (int) total;
    vector<long long> dp(k, 0);
    dp[0] = 1;
    for (int g : groups) {
        vector<long long> pre(k + 1, 0);
        for (int s = 0; s < k; s++) pre[s + 1] = (pre[s] + dp[s]) % MOD;
        vector<long long> nd(k, 0);
        for (int s = 0; s < k; s++) nd[s] = (pre[s] - pre[max(0, s - g)] + MOD) % MOD;
        dp = nd;
    }
    long long bad = 0;
    for (long long x : dp) bad = (bad + x) % MOD;
    return (int) ((total - bad + MOD) % MOD);
}

JavaScript

var possibleStringCount = function(word, k) {
    var MOD = 1000000007;
    var groups = [];
    for (var i = 0; i < word.length;) {
        var j = i;
        while (j < word.length && word.charAt(j) === word.charAt(i)) j++;
        groups.push(j - i);
        i = j;
    }
    var total = 1;
    for (var a = 0; a < groups.length; a++) total = (total * groups[a]) % MOD;
    if (groups.length >= k) return total;
    var dp = new Array(k).fill(0);
    dp[0] = 1;
    for (var b = 0; b < groups.length; b++) {
        var g = groups[b];
        var pre = new Array(k + 1).fill(0);
        for (var s = 0; s < k; s++) pre[s + 1] = (pre[s] + dp[s]) % MOD;
        var nd = new Array(k).fill(0);
        for (var t = 0; t < k; t++) nd[t] = (pre[t] - pre[Math.max(0, t - g)] + MOD) % MOD;
        dp = nd;
    }
    var bad = 0;
    for (var u = 0; u < k; u++) bad = (bad + dp[u]) % MOD;
    return (total - bad + MOD) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard