Find the Original Typed String II
Source: leetcode
Difficulty: Hard
Tags: string, dynamic-programming, prefix-sum

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`.


 


**Example 1:**



**Input:** word \= "aabbccdd", k \= 7


**Output:** 5


**Explanation:**


The possible strings are: `"aabbccdd"`, `"aabbccd"`, `"aabbcdd"`, `"aabccdd"`, and `"abbccdd"`.



**Example 2:**



**Input:** word \= "aabbccdd", k \= 8


**Output:** 1


**Explanation:**


The only possible string is `"aabbccdd"`.



**Example 3:**



**Input:** word \= "aaabbb", k \= 3


**Output:** 8



 


**Constraints:**


- `1 <= word.length <= 5 * 105`
- `word` consists only of lowercase English letters.
- `1 <= k <= 2000`




C++ solution:
class Solution {
public:
    int possibleStringCount(string word, int k) {
        int n = word.length();
        long long total = 1;
        const long long mod = 1e9 + 7;
        vector<int> segments;
        int cnt = 1;

        // Step 1: Segment consecutive identical characters in `word`
        // For example, if word = "aaabbc", segments will store [3, 2, 1]
        for (int i = 1; i < n; i++) {
            if (word[i] != word[i - 1]) {
                segments.push_back(cnt);  // Store the length of current segment
                cnt = 1;  // Reset count for new segment
            } else {
                cnt++;  // Increment count for consecutive character
            }
        }
        segments.push_back(cnt);  // Add the last segment count

        // Step 2: Calculate `total`, the product of all segment sizes (modulo `mod`)
        // This represents the total possible combinations considering each segment individually
        for (int i = 0; i < segments.size(); i++) {
            total = (total * segments[i]) % mod;
        }

        // Step 3: Initialize the first row of dynamic programming table `prev_row`
        // `prev_row[x]` represents the number of ways to form a valid substring
        // ending with `x` characters from the first segment.
        vector<int> prev_row(k + 1, 0);
        for (int x = 1; x <= min(segments[0], k - 1); x++) {
            prev_row[x] = 1;  // Set ways to 1 for initial segment
        }

        // Initialize temporary vectors for calculations in later segments
        vector<int> curr_row(k + 1, 0);   // Stores ways for the current segment
        vector<int> prefix(k + 1, 0);     // Stores cumulative sums for efficient range calculations

        int a = segments.size();  // Number of segments
        // Step 4: Process each subsequent segment up to `k` segments (to avoid over-calculation)
        for (int i = 1; i < min(a, k); i++) {     
            // Compute cumulative sums in `prefix` for `prev_row`
            prefix[0] = prev_row[0];
            for (int x = 1; x <= k; x++) {
                prefix[x] = (prefix[x - 1] + prev_row[x]) % mod;  // Prefix sum mod `mod`
            }

            // Calculate current row `curr_row` using prefix sums
            for (int x = 1; x <= k; x++) {
                int prev_point = max(x - segments[i], i);
                // Calculate ways for current position x using the prefix array
                curr_row[x] = (prefix[x - 1] - prefix[prev_point - 1] + mod) % mod;
            }
            prev_row = curr_row;  // Move current row to previous row for next iteration
        }

        // Step 5: Calculate `t2`, which is the sum of possible substrings of length `k`
        long long t2 = 0;
        for (int i = 0; i < k; i++) {
            t2 = (t2 + prev_row[i]) % mod;
        }

        // Step 6: Return the result as (total - t2) modulo `mod`
        // `total` is all combinations, and `t2` removes those not meeting the criteria
        return (total - t2 + mod) % mod;
    }
};

Go solution:
const Modulo = 1000000007

func possibleStringCount(word string, k int) int {
    i, m, n := 0, 0, len(word)
    switch {
        case n < k:
        return 0
        case n == k:
        return 1
    }
    res := int64(1) // total number of possible strings
    dp := make([]int, k)
    dp2 := make([]int, k)
    dp[0] = 1 // empty string
    for ; i < n && m < k; i++ {
        m++ // number of groups
        c := 1 // size of current group
        for i < n - 1 && word[i] == word[i + 1] {
            i++
            c++
        }
        res = (res * int64(c)) % Modulo
        s := 0 // sliding window sum
        for j := m - 1; j < k && j < m + c - 1; j++ {
            dp2[j] = s
            s = (s + dp[j]) % Modulo
        }
        for j := m + c - 1; j < k; j++ {
            dp2[j] = s
            s = (s + Modulo - dp[j - c]) % Modulo
            s = (s + dp[j]) % Modulo
        }
        dp, dp2 = dp2, dp
        dp2[m - 1] = 0
    }
    for i < n {
        i++
        c := int64(1)
        for i < n && word[i] == word[i - 1] {
            i++
            c++
        }
        res = (res * c) % Modulo
    }
    s := 0 // total number of strings with length less than k
    for _, v := range dp {
        s = (s + v) % Modulo
    }
    return int((res + Modulo - int64(s)) % Modulo)
}

Java solution:
class Solution {
    public int possibleStringCount(String word, int k) {
        final int MODULO = (int) (1e9 + 7);
        int wordLength = word.length();
        List<Integer> characterGroups = new ArrayList<>();
        
        for (int index = 0; index < wordLength;) {
            int characterCount = 1;
            char currentCharacter = word.charAt(index++);
            while (index < wordLength && word.charAt(index) == currentCharacter) {
                characterCount++;
                index++;
            }
            characterGroups.add(characterCount);
        }

        long totalCombinations = 1;
        for (int groupCount : characterGroups) {
            totalCombinations = (totalCombinations * groupCount) % MODULO;
        }

        if (k <= characterGroups.size()) {
            return (int) totalCombinations;
        }

        int maxSize = k - 1;
        int[] dp = new int[maxSize + 1];
        dp[0] = 1;

        for (int count : characterGroups) {
            int[] newDP = new int[maxSize + 1];
            long cumulativeSum = 0;
            for (int s = 0; s <= maxSize; s++) {
                if (s - 1 >= 0) cumulativeSum = (cumulativeSum + dp[s - 1]) % MODULO;
                if (s - count - 1 >= 0) cumulativeSum = (cumulativeSum - dp[s - count - 1] + MODULO) % MODULO;
                newDP[s] = (int) cumulativeSum;
            }
            dp = newDP;
        }

        long totalLessThanK = 0;
        for (int s = characterGroups.size(); s <= maxSize; s++) {
            totalLessThanK = (totalLessThanK + dp[s]) % MODULO;
        }

        return (int) ((totalCombinations - totalLessThanK + MODULO) % MODULO);
    }
}

JavaScript solution:
function possibleStringCount(word, k) {
  const mod = 1000000007;
  const n = word.length;
  let groups = [];
  let cnt = 1;
  for (let i = 1; i < n; i++) {
    if (word[i] === word[i - 1]) {
      cnt++;
    } else {
      groups.push(cnt);
      cnt = 1;
    }
  }
  groups.push(cnt);
  const r = groups.length;
  let total = 1;
  for (const L of groups) {
    total = (total * L) % mod;
  }
  if (r >= k) return total;
  let dp = new Array(k).fill(0);
  dp[0] = 1;
  for (let g = 0; g < groups.length; g++) {
    const L = groups[g];
    let newdp = new Array(k).fill(0);
    let prefix = new Array(k).fill(0);
    prefix[0] = dp[0] % mod;
    for (let j = 1; j < k; j++) {
      prefix[j] = (prefix[j - 1] + dp[j]) % mod;
    }
    for (let j = 0; j < k; j++) {
      if (j === 0) continue;
      const t = j < L ? j : L;
      let sumVal = prefix[j - 1];
      if (j - t - 1 >= 0) sumVal = (sumVal - prefix[j - t - 1] + mod) % mod;
      newdp[j] = sumVal;
    }
    dp = newdp;
  }
  let invalid = 0;
  for (let j = 0; j < k; j++) {
    invalid = (invalid + dp[j]) % mod;
  }
  return (total - invalid + mod) % mod;
}

Python solution:
mod_mul = lambda a, b: (a * b) % 1_000_000_007
mod_add = lambda a, b: (a + b) % 1_000_000_007
mod_sub = lambda a, b: (a - b) % 1_000_000_007

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int: 
        segs = [1]
        for i in range(1, len(word)):
            if word[i] != word[i-1]:
                segs.append(1)
            else:
                segs[-1] += 1
        total = reduce(mod_mul, segs)
        if k <= len(segs):
            return total
        
        dp = [1] + ([0] * (k-1))
        for i in range(1, len(segs)+1):
            prefix = list(accumulate(dp, mod_add, initial=0))
            dp = [0] * k
            for j in range(i, k):
                dp[j] = mod_sub(prefix[j], prefix[j - min(segs[i-1], j-i+1)])
        less_than_k = reduce(mod_add, dp)
        return mod_sub(total, less_than_k)

Ruby solution:
def possible_string_count(word, k)
  mod = 1000000007
  n = word.size
  groups = []
  cnt = 1
  (1...n).each do |i|
    if word[i] == word[i-1]
      cnt += 1
    else
      groups << cnt
      cnt = 1
    end
  end
  groups << cnt
  m = groups.size
  total = 1
  groups.each { |g| total = (total * g) % mod }
  return total if m >= k
  t = k - m
  dp = Array.new(t, 0)
  dp[0] = 1
  groups.each do |g|
    d = g - 1
    new_dp = Array.new(t, 0)
    prefix = Array.new(t, 0)
    prefix[0] = dp[0] % mod
    (1...t).each { |j| prefix[j] = (prefix[j-1] + dp[j]) % mod }
    (0...t).each do |v|
      if v <= d
        new_dp[v] = prefix[v] % mod
      else
        new_dp[v] = (prefix[v] - prefix[v-d-1]) % mod
      end
    end
    dp = new_dp
  end
  invalid = dp.inject(0) { |s, x| (s + x) % mod }
  (total - invalid) % mod
end