LeetCode 3333: Find the Original Typed String II

Explanation:

To solve this problem, we can use dynamic programming. We will iterate through the characters of the given string word and keep track of the number of ways to construct strings of length i ending at that character.

We will maintain a 2D array dp where dp[i][j] represents the number of ways to construct strings of length i ending at the j-th character of the input string word. The transition equation to update dp[i][j] is based on the previous counts at dp[i-1][j] and also considers the count from the previous character dp[i-1][j-1].

Finally, we sum up the counts for strings of length k to the length of the input string word to get the total possible original strings that Alice might have intended to type.

:

class Solution {
    public int findTypedString(String word, int k) {
        int mod = 1000000007;
        int n = word.length();
        long[][] dp = new long[k+1][n+1];
        
        for (int i = 1; i <= n; i++) {
            dp[1][i] = 1;
        }
        
        for (int i = 2; i <= k; i++) {
            long sum = 0;
            for (int j = 1; j <= n; j++) {
                sum = (sum + dp[i-1][j]) % mod;
                dp[i][j] = (dp[i][j-1] + sum) % mod;
            }
        }
        
        long result = 0;
        for (int i = k; i <= n; i++) {
            result = (result + dp[k][i]) % mod;
        }
        
        return (int)result;
    }
}