Count Number of Texts

medium dp string

Problem

On an old phone keypad each digit maps to letters: 2 to 6 and 8 give 3 letters each, while 7 and 9 give 4 letters. To type a letter you press its digit once for the first letter, twice for the second, and so on. Given a string pressedKeys of the keys Alice actually pressed, count how many distinct text messages those presses could spell out. Return the count modulo 1000000007.

InputpressedKeys = "22233"

Output8

The run "222" can be read 4 ways (aaa, ab, ba, c) and "33" can be read 2 ways (dd, e), so 4 × 2 = 8.

pressedKeys (digits 2-9)

def count_texts(pressed_keys):
    MOD = 10**9 + 7
    s = pressed_keys
    total, i, n = 1, 0, len(s)
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        run = j - i
        k = 4 if s[i] in "79" else 3
        dp = [1] + [0] * run
        for x in range(1, run + 1):
            for t in range(1, k + 1):
                if x - t >= 0:
                    dp[x] = (dp[x] + dp[x - t]) % MOD
        total = (total * dp[run]) % MOD
        i = j
    return total

function countTexts(pressedKeys) {
  const MOD = 1000000007n;
  const s = pressedKeys, n = s.length;
  let total = 1n, i = 0;
  while (i < n) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    const run = j - i;
    const k = (s[i] === "7" || s[i] === "9") ? 4 : 3;
    const dp = new Array(run + 1).fill(0n);
    dp[0] = 1n;
    for (let x = 1; x <= run; x++) {
      for (let t = 1; t <= k; t++) {
        if (x - t >= 0) dp[x] = (dp[x] + dp[x - t]) % MOD;
      }
    }
    total = (total * dp[run]) % MOD;
    i = j;
  }
  return Number(total);
}

class Solution {
    public int countTexts(String pressedKeys) {
        long MOD = 1000000007L;
        String s = pressedKeys;
        int n = s.length(), i = 0;
        long total = 1;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            int run = j - i;
            int k = (s.charAt(i) == '7' || s.charAt(i) == '9') ? 4 : 3;
            long[] dp = new long[run + 1];
            dp[0] = 1;
            for (int x = 1; x <= run; x++) {
                for (int t = 1; t <= k; t++) {
                    if (x - t >= 0) dp[x] = (dp[x] + dp[x - t]) % MOD;
                }
            }
            total = (total * dp[run]) % MOD;
            i = j;
        }
        return (int) total;
    }
}

int countTexts(string pressedKeys) {
    const long long MOD = 1000000007LL;
    string s = pressedKeys;
    int n = s.size(), i = 0;
    long long total = 1;
    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        int run = j - i;
        int k = (s[i] == '7' || s[i] == '9') ? 4 : 3;
        vector<long long> dp(run + 1, 0);
        dp[0] = 1;
        for (int x = 1; x <= run; x++) {
            for (int t = 1; t <= k; t++) {
                if (x - t >= 0) dp[x] = (dp[x] + dp[x - t]) % MOD;
            }
        }
        total = (total * dp[run]) % MOD;
        i = j;
    }
    return (int) total;
}

Explanation

Look at what Alice typed as runs of the same digit. Two different digits can never be confused, so the message splits cleanly at every place the digit changes. The total number of possible messages is just the product of the ways to read each run on its own.

Now zoom into one run, say k identical presses of the digit 2. The first letter of that run was typed by pressing 2 either once (for a), twice (for b), or three times (for c). After we "use up" 1, 2, or 3 of the presses for that first letter, the rest of the run is a smaller version of the same problem.

That gives a recurrence that looks exactly like Tribonacci: f(x) = f(x-1) + f(x-2) + f(x-3), with f(0) = 1 (one way to type nothing). For the keys 7 and 9 there are four letters, so a press could account for 1, 2, 3, or 4 letters and the recurrence sums the previous four values instead of three.

Example: pressedKeys = "22233". The run "222" gives f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4 ways. The run "33" gives f(2) = f(1) + f(0) = 2 ways. Multiplying, 4 × 2 = 8 distinct messages.

Everything is done modulo 1000000007 because the count can grow very large. Each run is processed in time linear to its length, so the whole pass is linear overall.

Time: O(n) Space: O(n)