Find the original typed string ii

String Dynamic Programming Prefix Sum

45.6% acceptance

Feb 23, 2026

503

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times. You are given a string word, which represents the final output displayed on Alice's screen. You are also given a positive integer k. Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn possible_string_count(word: String, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let w = word.as_bytes();
    let n = w.len();
    let k = k as usize;

    // Parse groups of consecutive identical chars
    let mut groups: Vec<usize> = Vec::new();
    let mut i = 0;
    while i < n {
      let mut j = i;
      while j < n && w[j] == w[i] { j += 1; }
      groups.push(j - i);
      i = j;
    }

    let m = groups.len();
    // Total original strings = product of group lengths
    let total: i64 = groups.iter().fold(1i64, |acc, &g| acc * g as i64 % MOD);

    // If k <= m, minimum original length = m >= k, so all strings are valid
    if k <= m {
      return total as i32;
    }

    // Count strings with length LESS than k, then subtract from total.
    // dp[len] = number of ways to pick one value from each group seen so far
    //           such that the sum of chosen values equals len.
    // Each group i contributes a value in 1..=groups[i].
    // We only care about len in 0..k.
    let mut dp = vec![0i64; k];
    dp[0] = 1;

    for &g in &groups {
      // ndp[j] = sum of dp[j - v] for v in 1..=min(g, j)
      //        = prefix[j] - prefix[max(0, j - g)]
      let mut psum = vec![0i64; k + 1];
      for j in 0..k {
        psum[j + 1] = (psum[j] + dp[j]) % MOD;
      }
      let mut ndp = vec![0i64; k];
      for j in 1..k {
        let lo = if j > g { j - g } else { 0 };
        ndp[j] = (psum[j] - psum[lo] + MOD) % MOD;
      }
      dp = ndp;
    }

    let too_short: i64 = dp.iter().sum::<i64>() % MOD;
    ((total - too_short + MOD) % MOD) as i32
  }
}