We're back with another tricky typing challenge — and this time, it’s the harder version of the original “clumsy typing” problem. In this task, Alice is still prone to pressing keys for too long, but now we’re required to find how many intended strings of length at least k could have led to the observed string. It’s a twist that requires both dynamic programming and smart counting!
Let’s decode it, step by step. 🔍
🧠 Problem Summary
You're given:
- A string
wordwhich may contain characters typed multiple times consecutively. - An integer
k, representing the minimum possible original string length.
Your goal:
Return the total number of possible original strings that Alice may have intended to type, with size at least
k.
Since the result can be large, return it modulo $10^9 + 7$.
💡 Intuition
Every group of repeated characters (like aa or ccc) can be compressed into one character by treating some repeated keystrokes as mistakes.
So for a group of length g, you can pick from 1 to g characters as your intended character. That means g choices. Multiply all such choices for all groups and we get the total number of possible intended strings.
However, we are asked to only count the ones of size at least k.
So the final result is:
- Total number of all valid strings formed by reducing groups.
- Minus the number of those which are shorter than
k— and this is calculated using dynamic programming.
🛠️ C++ Code
class Solution {
public:
int possibleStringCount(string word, int k) {
vector<int> cnt;
int64_t total = 1, mod = 1e9+7;
for (int i = 0; i < word.size();){
int j = i;
while (++i < word.size())
if (word[i] != word[j]) break;
if (i > j+1) {
cnt.push_back(i-j-1);
total = total * (i-j) % mod;
}
k--;
}
if (k <= 0) return total;
vector<int64_t> dp(k,0);
dp[0] = 1;
for (int c : cnt){
for (int i = 1; i < k; i++)
dp[i] = (dp[i] + dp[i-1]) % mod;
for (int i = k-1; i > c; i--)
dp[i] = (dp[i] - dp[i-c-1] + mod) % mod;
}
for (int i = 1; i < k; i++)
dp[i] = (dp[i] + dp[i-1]) % mod;
return (total - dp[k-1] + mod) % mod;
}
};
🐍 Python Code
class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
mod = 10**9 + 7
cnt = []
total = 1
i = 0
while i < len(word):
j = i
while i < len(word) and word[i] == word[j]:
i += 1
if i > j + 1:
cnt.append(i - j - 1)
total = total * (i - j) % mod
k -= 1
if k <= 0:
return total
dp = [0] * k
dp[0] = 1
for c in cnt:
for i in range(1, k):
dp[i] = (dp[i] + dp[i - 1]) % mod
for i in range(k - 1, c, -1):
dp[i] = (dp[i] - dp[i - c - 1]) % mod
for i in range(1, k):
dp[i] = (dp[i] + dp[i - 1]) % mod
return (total - dp[k - 1]) % mod
💻 JavaScript Code
var possibleStringCount = function(word, k) {
const mod = 1e9 + 7;
let cnt = [], total = 1;
for (let i = 0; i < word.length;) {
let j = i;
while (++i < word.length && word[i] === word[j]);
if (i > j + 1) {
cnt.push(i - j - 1);
total = total * (i - j) % mod;
}
k--;
}
if (k <= 0) return total;
let dp = Array(k).fill(0);
dp[0] = 1;
for (let c of cnt) {
for (let i = 1; i < k; i++)
dp[i] = (dp[i] + dp[i - 1]) % mod;
for (let i = k - 1; i > c; i--)
dp[i] = (dp[i] - dp[i - c - 1] + mod) % mod;
}
for (let i = 1; i < k; i++)
dp[i] = (dp[i] + dp[i - 1]) % mod;
return (total - dp[k - 1] + mod) % mod;
};
📝 Key Takeaways
- Group same characters and calculate how many ways each group can reduce.
- Use prefix sum-style dynamic programming to count how many strings are shorter than
k. - Subtract to get only those of length
≥ k.
✅ Final Thoughts
This problem is an elegant combination of combinatorics + DP, and gives great practice in optimizing string operations. A great leap from Part I!
Let me know if you want a visual version or explanation video. Until then — happy coding! 🚀