🏂Beginner-Friendly Guide "Find the Original Typed String II" – LeetCode 3333 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

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 word which 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.