3333. Find the Original Typed String II

Description

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(groups.length*k+n)
• Space complexity: O(groups.length+k)

 

JavaScript

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
const possibleStringCount = function (word, k) {
  const MODULO = BigInt(10 ** 9 + 7);
  const n = word.length;
  const groups = [];
  let group = 1n;

  for (let index = 1; index <= n; index++) {
    if (word[index] === word[index - 1]) {
      group += 1n;
    } else {
      groups.push(group);
      group = 1n;
    }
  }

  const combinations = groups.reduce((total, group) => (total * group) % MODULO, 1n);

  if (groups.length >= k) return Number(combinations);

  let dp = Array.from({ length: k + 1 }, () => 0n);

  dp[1] = 1n;

  for (const [index, group_] of groups.entries()) {
    const nextDp = new Array(k + 1).fill(0n);
    const group = Number(group_);
    let sumCount = 0n;

    for (let len = index + 1; len <= k; len++) {
      nextDp[len] = (nextDp[len] + sumCount) % MODULO;
      sumCount = (sumCount + dp[len]) % MODULO;

      if (len > group) {
        const overCount = dp[len - group];

        sumCount = (sumCount - overCount + MODULO) % MODULO;
      }
    }

    dp = nextDp;
  }

  const invalidCombinations = dp.reduce((total, count) => (total + count) % MODULO);

  return Number((combinations - invalidCombinations + MODULO) % MODULO);
};