Count Number of Texts

Medium
1042.

Count Number of Texts

Count Number of Texts is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Flipkart interviews.

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'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} pressedKeys
 * @return {number}
 */
var countTexts = function(pressedKeys) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Texts — Solution in Python, Java & C++

Count Number of Texts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Texts is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Flipkart interviews.

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'.

Hints for Count Number of Texts

  1. Hint 1

    Runs of different digits are independent — multiply their counts.

  2. Hint 2

    For a run of length L on a three-letter key, the count obeys f(L) = f(L-1) + f(L-2) + f(L-3) — a tribonacci.

  3. Hint 3

    Keys 7 and 9 add a fourth term, giving a tetranacci.

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

  1. 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.
  2. Walk the string, measuring each maximal run of one digit.
  3. 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

Java

public static int countTexts(String pressedKeys) {
    final long MOD = 1000000007L;
    int n = pressedKeys.length();
    long[] tri = new long[n + 1];
    long[] tet = new long[n + 1];
    tri[0] = 1;
    tet[0] = 1;
    for (int 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;
    }
    long answer = 1;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && pressedKeys.charAt(j) == pressedKeys.charAt(i)) j++;
        int len = j - i;
        char c = pressedKeys.charAt(i);
        answer = answer * (c == '7' || c == '9' ? tet[len] : tri[len]) % MOD;
        i = j;
    }
    return (int) answer;
}

C++

int countTexts(string pressedKeys) {
    const long long MOD = 1000000007LL;
    int n = (int) pressedKeys.size();
    vector<long long> tri(n + 1, 0), tet(n + 1, 0);
    tri[0] = 1;
    tet[0] = 1;
    for (int 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;
    }
    long long answer = 1;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && pressedKeys[j] == pressedKeys[i]) j++;
        int len = j - i;
        char c = pressedKeys[i];
        answer = answer * ((c == '7' || c == '9') ? tet[len] : tri[len]) % MOD;
        i = j;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets