Count Number of Texts — Medium Problem & Solution

On an old phone keypad, a letter is typed by pressing its key repeatedly: key 2 gives a, b, c for one, two or three presses; 7 gives p, q, r, s for one to…

Difficulty: Medium
Topics: Strings, Math, Hash Table, Dynamic Programming
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

On an old phone keypad, a letter is typed by pressing its key repeatedly: key 2 gives a, b, c for one, two or three presses; 7 gives p, q, r, s for one to four; and so on. Keys 7 and 9 carry four letters, every other key carries three.

Given the sequence of key presses pressedKeys, return how many different messages could have produced it, modulo 10⁹ + 7.

Example 1

Input: pressedKeys = "22233"
Output: 8
Explanation: The run `222` splits 4 ways and `33` splits 2 ways.

Example 2

Input: pressedKeys = "2"
Output: 1
Explanation: Only `a`.

Example 3

Input: pressedKeys = "7777"
Output: 8
Explanation: Key 7 has four letters, so the run of four splits 8 ways.

Constraints

1 <= pressedKeys.length <= 10^5
pressedKeys only consists of digits from '2' - '9'.

How to solve Count Number of Texts

Split the string into maximal runs of one digit. A run is decoded by cutting it into pieces of 1, 2, 3 (or up to 4 for keys 7 and 9) presses, so the number of ways is the tribonacci — or tetranacci — value at the run's length. Multiply across runs.

Approach

Precompute tri[i] = tri[i-1] + tri[i-2] + tri[i-3] and tet[i] with a fourth term, both with f(0) = 1 and negative indices treated as 0.
Walk the string, measuring each maximal run of one digit.
Multiply the running answer by tet[len] for 7 and 9, and by tri[len] otherwise.

Why it works

Runs cannot interact: a cut is forced at every digit change, because two different keys can never form one letter. Within a run, the recurrence follows from choosing how many presses the last letter consumes — 1, 2, 3 (or 4) — which is exactly the tribonacci/tetranacci structure.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Keys 7 and 9 have four letters; treating every key as three under-counts.
f(0) = 1 — an empty remainder has exactly one decoding.
The product must be taken modulo 10⁹ + 7 at every step.

Reference solution

Python

def countTexts(pressedKeys: str) -> int:
    MOD = 10**9 + 7
    n = len(pressedKeys)
    tri = [0] * (n + 1)
    tet = [0] * (n + 1)
    tri[0] = tet[0] = 1
    for i in range(1, n + 1):
        tri[i] = tri[i - 1]
        tet[i] = tet[i - 1]
        if i >= 2:
            tri[i] = (tri[i] + tri[i - 2]) % MOD
            tet[i] = (tet[i] + tet[i - 2]) % MOD
        if i >= 3:
            tri[i] = (tri[i] + tri[i - 3]) % MOD
            tet[i] = (tet[i] + tet[i - 3]) % MOD
        if i >= 4:
            tet[i] = (tet[i] + tet[i - 4]) % MOD
    answer = 1
    i = 0
    while i < n:
        j = i
        while j < n and pressedKeys[j] == pressedKeys[i]:
            j += 1
        length = j - i
        answer = answer * (tet[length] if pressedKeys[i] in "79" else tri[length]) % MOD
        i = j
    return answer

JavaScript

var countTexts = function(pressedKeys) {
    var MOD = 1000000007;
    var n = pressedKeys.length, i;
    var tri = [], tet = [];
    for (i = 0; i <= n; i++) { tri.push(0); tet.push(0); }
    tri[0] = 1; tet[0] = 1;
    for (i = 1; i <= n; i++) {
        tri[i] = tri[i - 1];
        tet[i] = tet[i - 1];
        if (i >= 2) { tri[i] = (tri[i] + tri[i - 2]) % MOD; tet[i] = (tet[i] + tet[i - 2]) % MOD; }
        if (i >= 3) { tri[i] = (tri[i] + tri[i - 3]) % MOD; tet[i] = (tet[i] + tet[i - 3]) % MOD; }
        if (i >= 4) tet[i] = (tet[i] + tet[i - 4]) % MOD;
    }
    var answer = 1;
    i = 0;
    while (i < n) {
        var j = i;
        while (j < n && pressedKeys.charAt(j) === pressedKeys.charAt(i)) j++;
        var len = j - i;
        var c = pressedKeys.charAt(i);
        var ways = c === "7" || c === "9" ? tet[len] : tri[len];
        var mhi = Math.floor(answer / 65536), mlo = answer % 65536;
        answer = ((mhi * ways % MOD) * 65536 + mlo * ways) % MOD;
        i = j;
    }
    return answer;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue