Find the Original Typed String II solution and explanation

MOD = 10**9 + 7

def possible_original_strings(word, k):
    n = len(word)
    dp = [0] * (n + 1)
    dp[n] = 1
    
    for i in range(n - 1, -1, -1):
        dp[i] = dp[i + 1]
        if i < n - 1 and word[i] == word[i + 1]:
            dp[i] = (dp[i] + dp[i + 2]) % MOD

    return sum(dp[i] for i in range(k, n + 1)) % MOD

# Example usage
word = "aabbccdd"
k = 7
print(possible_original_strings(word, k))

const MOD = 1e9 + 7;

function possibleOriginalStrings(word, k) {
    const n = word.length;
    const dp = Array(n + 1).fill(0);
    dp[n] = 1;

    for (let i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];
        if (i < n - 1 && word[i] === word[i + 1]) {
            dp[i] = (dp[i] + dp[i + 2]) % MOD;
        }
    }

    let result = 0;
    for (let i = k; i <= n; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

// Example usage
const word = "aabbccdd";
const k = 7;
console.log(possibleOriginalStrings(word, k));

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int possibleOriginalStrings(const string &word, int k) {
    int n = word.size();
    vector<int> dp(n + 1, 0);
    dp[n] = 1;

    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];
        if (i < n - 1 && word[i] == word[i + 1]) {
            dp[i] = (dp[i] + dp[i + 2]) % MOD;
        }
    }

    int result = 0;
    for (int i = k; i <= n; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

int main() {
    string word = "aabbccdd";
    int k = 7;
    cout << possibleOriginalStrings(word, k) << endl;
    return 0;
}

#include <stdio.h>
#define MOD 1000000007

int possibleOriginalStrings(const char *word, int k) {
    int n = strlen(word);
    int dp[n + 1];
    dp[n] = 1;
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];
        if (i < n - 1 && word[i] == word[i + 1]) {
            dp[i] = (dp[i] + (i + 2 < n ? dp[i + 2] : 1)) % MOD;
        }
    }

    int result = 0;
    for (int i = k; i <= n; i++) {
        result = (result + dp[i]) % MOD;
    }
    return result;
}

int main() {
    const char *word = "aabbccdd";
    int k = 7;
    printf("%d\n", possibleOriginalStrings(word, k));
    return 0;
}

class Solution {
    public int possibleStringCount(String word, int k) {
        final int mod = (int) 1e9 + 7;
        List<Integer> nums = new ArrayList<>();
        long ans = 1;
        int cur = 0;
        int n = word.length();

        for (int i = 0; i < n; i++) {
            cur++;
            if (i == n - 1 || word.charAt(i) != word.charAt(i + 1)) {
                if (cur > 1) {
                    if (k > 0) {
                        nums.add(cur - 1);
                    }
                    ans = ans * cur % mod;
                }
                cur = 0;
                k--;
            }
        }

        if (k < 1) {
            return (int) ans;
        }

        int m = nums.size();
        int[][] f = new int[m + 1][k];
        f[0][0] = 1;

        for (int i = 1; i <= m; i++) {
            int x = nums.get(i - 1);
            long[] s = new long[k + 1];
            for (int j = 0; j < k; j++) {
                s[j + 1] = (s[j] + f[i - 1][j]) % mod;
            }
            for (int j = 0; j < k; j++) {
                int l = Math.max(0, j - x);
                f[i][j] = (int) ((s[j + 1] - s[l] + mod) % mod);
            }
        }

        long sum = 0;
        for (int j = 0; j < k; j++) {
            sum = (sum + f[m][j]) % mod;
        }

        return (int) ((ans - sum + mod) % mod);
    }
}

function possibleStringCount(word: string, k: number): number {
    const mod = 1_000_000_007;
    const nums: number[] = [];
    let ans = 1;
    let cur = 0;
    const n = word.length;

    for (let i = 0; i < n; i++) {
        cur++;
        if (i === n - 1 || word[i] !== word[i + 1]) {
            if (cur > 1) {
                if (k > 0) {
                    nums.push(cur - 1);
                }
                ans = (ans * cur) % mod;
            }
            cur = 0;
            k--;
        }
    }

    if (k < 1) {
        return ans;
    }

    const m = nums.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(k).fill(0));
    f[0][0] = 1;

    for (let i = 1; i <= m; i++) {
        const x = nums[i - 1];
        const s: number[] = Array(k + 1).fill(0);
        for (let j = 0; j < k; j++) {
            s[j + 1] = (s[j] + f[i - 1][j]) % mod;
        }
        for (let j = 0; j < k; j++) {
            const l = Math.max(0, j - x);
            f[i][j] = (s[j + 1] - s[l] + mod) % mod;
        }
    }

    let sum = 0;
    for (let j = 0; j < k; j++) {
        sum = (sum + f[m][j]) % mod;
    }

    return (ans - sum + mod) % mod;
}

func possibleStringCount(word string, k int) int {
	const mod = 1_000_000_007
	nums := []int{}
	ans := 1
	cur := 0
	n := len(word)

	for i := 0; i < n; i++ {
		cur++
		if i == n-1 || word[i] != word[i+1] {
			if cur > 1 {
				if k > 0 {
					nums = append(nums, cur-1)
				}
				ans = ans * cur % mod
			}
			cur = 0
			k--
		}
	}

	if k < 1 {
		return ans
	}

	m := len(nums)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, k)
	}
	f[0][0] = 1

	for i := 1; i <= m; i++ {
		x := nums[i-1]
		s := make([]int, k+1)
		for j := 0; j < k; j++ {
			s[j+1] = (s[j] + f[i-1][j]) % mod
		}
		for j := 0; j < k; j++ {
			l := j - x
			if l < 0 {
				l = 0
			}
			f[i][j] = (s[j+1] - s[l] + mod) % mod
		}
	}

	sum := 0
	for j := 0; j < k; j++ {
		sum = (sum + f[m][j]) % mod
	}

	return (ans - sum + mod) % mod
}