2266. Count Number of Texts

Hash Table
Math
String
Dynamic Programming

TIME

O(n)

SPACE

O(n)

Intuition

A run of the same digit can be broken into letters independently of the other runs (a different digit forces a boundary). So the total is the product over runs of "how many ways this run splits into letters".

Within a run of length L, each letter is one press-group of size 1..m, where m = 4 for keys 7 and 9 (they have four letters), and m = 3 for the rest. Counting the ways to tile a length-L strip with pieces of size 1..m is the tribonacci (m = 3) or tetranacci (m = 4) recurrence:

dp3[i] = dp3[i-1] + dp3[i-2] + dp3[i-3]
dp4[i] = dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]

Approach

Precompute dp3 and dp4 up to n (mod 1e9 + 7), with base cases dp[0] = 1.
Scan pressedKeys, grouping maximal runs of equal digits.
For each run, multiply the answer by dp4[len] if the digit is 7 or 9, else dp3[len].
Return the product modulo 1e9 + 7.

Complexity

Time: O(n), precompute tables and one scan
Space: O(n), the DP tables

Edge Cases

Single-character run → 1 way
Long uniform run of 2 → pure tribonacci (Example 2)
Keys 7 and 9 use the 4-term recurrence; all others the 3-term
Apply the modulus throughout to avoid overflow (long in Java)
Base cases dp[0] = dp[1] = 1, dp[2] = 2, etc., must be seeded correctly

Code

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        """
        2266. Count Number of Texts
        Time: O(n)
        Space: O(n)
        """
        MOD = 10**9 + 7
        n = len(pressedKeys)

        # dp3: tile length i with pieces 1..3; dp4: pieces 1..4.
        dp3 = [0] * (n + 1)
        dp4 = [0] * (n + 1)
        dp3[0] = dp4[0] = 1
        for i in range(1, n + 1):
            dp3[i] = (dp3[i - 1] + (dp3[i - 2] if i >= 2 else 0) + (dp3[i - 3] if i >= 3 else 0)) % MOD
            dp4[i] = (dp4[i - 1] + (dp4[i - 2] if i >= 2 else 0)
                      + (dp4[i - 3] if i >= 3 else 0) + (dp4[i - 4] if i >= 4 else 0)) % MOD

        ans = 1
        i = 0
        while i < n:
            j = i
            while j < n and pressedKeys[j] == pressedKeys[i]:
                j += 1
            run = j - i
            table = dp4 if pressedKeys[i] in "79" else dp3
            ans = ans * table[run] % MOD
            i = j
        return ans

/**
 * 2266. Count Number of Texts
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    private static final int MOD = 1_000_000_007;

    public int countTexts(String pressedKeys) {
        int n = pressedKeys.length();

        // dp3: tile length i with pieces 1..3; dp4: pieces 1..4.
        long[] dp3 = new long[n + 1];
        long[] dp4 = new long[n + 1];
        dp3[0] = dp4[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp3[i] = dp3[i - 1];
            if (i >= 2) dp3[i] += dp3[i - 2];
            if (i >= 3) dp3[i] += dp3[i - 3];
            dp3[i] %= MOD;

            dp4[i] = dp4[i - 1];
            if (i >= 2) dp4[i] += dp4[i - 2];
            if (i >= 3) dp4[i] += dp4[i - 3];
            if (i >= 4) dp4[i] += dp4[i - 4];
            dp4[i] %= MOD;
        }

        long ans = 1;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && pressedKeys.charAt(j) == pressedKeys.charAt(i)) {
                j++;
            }
            int run = j - i;
            char c = pressedKeys.charAt(i);
            long[] table = (c == '7' || c == '9') ? dp4 : dp3;
            ans = ans * table[run] % MOD;
            i = j;
        }
        return (int) ans;
    }
}