3333. Find the Original Typed String II

[mah-shamim]

Topics: 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

Hint:

1. Instead of solving for at least k, can we solve for at most k - 1 length?

[mah-shamim]

We need to determine the number of possible original strings Alice might have intended to type, given the final output string displayed on her screen and a positive integer k. The original string must be of length at least k. Alice may have pressed a key for too long, resulting in multiple consecutive characters in the output. The solution involves breaking down the problem into manageable parts and using dynamic programming to count valid configurations efficiently.

Approach

1. Problem Analysis:

   • The output string is formed by Alice possibly pressing keys for too long, leading to consecutive duplicate characters.
   • The original string is derived by reducing each consecutive run of identical characters in the output string to at least one character (but possibly more).
   • The goal is to count all such original strings where the total length is at least k.

2. Key Insight:

   • The problem can be decomposed by breaking the output string into consecutive runs of identical characters.
   • For each run of length l, the original string can have between 1 and l characters of that run.
   • The total number of possible original strings without any length constraint is the product of the lengths of all runs.
   • We need to subtract those original strings where the total length is less than k.

3. Dynamic Programming:

   • Use dynamic programming to count the number of original strings with total length less than k.
   • Initialize a DP array where dp[t] represents the number of ways to achieve a total length t after processing some runs.
   • For each run, update the DP array by considering all possible contributions (1 to l_i characters) from the current run.
   • Utilize prefix sums to optimize the DP updates, ensuring efficient computation.

4. Complexity Analysis:

   • Time Complexity: O(n * k), where n is the number of runs and k is the given constraint. This is because for each run, we process up to k elements in the DP array.
   • Space Complexity: O(k), as we maintain a DP array of size k and a prefix array of the same size.

Let's implement this solution in PHP: 3333. Find the Original Typed String II

<?php
/**
 * @param String $word
 * @param Integer $k
 * @return Integer
 */
function possibleStringCount($word, $k) {
    $MOD = 1000000007;
    $runs = $this->getRuns($word);
    $n_runs = count($runs);

    $total_ways = 1;
    foreach ($runs as $len) {
        $total_ways = (int)(((float)$total_ways * $len) % $MOD);
    }

    if ($k <= $n_runs) {
        return $total_ways;
    }

    $dp = array_fill(0, $k, 0);
    $dp[0] = 1;
    $min_index = 0;

    foreach ($runs as $l) {
        if ($min_index >= $k) {
            break;
        }

        $prefix = array_fill(0, $k, 0);
        $prefix[0] = $dp[0];
        for ($i = 1; $i < $k; $i++) {
            $prefix[$i] = ($prefix[$i-1] + $dp[$i]) % $MOD;
        }

        $new_dp = array_fill(0, $k, 0);
        $start_t = $min_index + 1;
        if ($start_t < $k) {
            for ($t = $start_t; $t < $k; $t++) {
                $term1 = $prefix[$t-1];
                $term2 = 0;
                $prev_index = $t - $l - 1;
                if ($prev_index >= 0) {
                    $term2 = $prefix[$prev_index];
                }
                $val = ($term1 - $term2) % $MOD;
                if ($val < 0) $val += $MOD;
                $new_dp[$t] = $val;
            }
        }

        $dp = $new_dp;
        $min_index++;
    }

    $F = 0;
    for ($i = 0; $i < $k; $i++) {
        $F = ($F + $dp[$i]) % $MOD;
    }

    $ans = ($total_ways - $F) % $MOD;
    if ($ans < 0) $ans += $MOD;
    return $ans;
}

/**
 * @param $word
 * @return array
 */
function getRuns($word) {
    $runs = array();
    $n = strlen($word);
    $i = 0;
    while ($i < $n) {
        $j = $i;
        while ($j < $n && $word[$j] == $word[$i]) {
            $j++;
        }
        $len = $j - $i;
        $runs[] = $len;
        $i = $j;
    }
    return $runs;
}

// Test cases
echo possibleStringCount("aabbccdd", 7) . "\n"; // Output: 5
echo possibleStringCount("aabbccdd", 8) . "\n"; // Output: 1
echo possibleStringCount("aaabbb", 3) . "\n";    // Output: 8
?>

Explanation:

1. Breaking into Runs: The function getRuns processes the input string to break it into consecutive runs of identical characters, storing the length of each run.
2. Total Ways Calculation: The total number of possible original strings without any length constraint is computed as the product of the lengths of all runs.
3. Dynamic Programming Setup: If k is less than or equal to the number of runs, the answer is simply the total ways since the minimum possible length of the original string is the number of runs.
4. DP Array Initialization: The DP array is initialized to keep track of the number of ways to achieve each possible total length up to k-1.
5. Processing Runs: For each run, the DP array is updated using prefix sums to efficiently compute the number of ways to form each possible total length by considering contributions from the current run.
6. Result Calculation: The result is obtained by subtracting the count of invalid strings (total length < k) from the total ways, ensuring the result is non-negative and modulo 10⁹ + 7.

This approach efficiently handles the constraints by leveraging dynamic programming and prefix sums to count valid configurations, ensuring optimal performance even for large inputs.

[topugit]

Thanks for solving the problem of "Find the Original Typed String II"

[mah-shamim]

Thanks