Count Number of Texts

Count Number of Texts

What is this problem about?

Imagine an old-school mobile keypad where letters are mapped to digits (e.g., '2' maps to "abc", '7' maps to "pqrs"). A user types a sequence of digits. You need to find the total number of possible text messages that could have been sent. For instance, "22" could be "aa" (pressed 2 once, twice) or "b" (pressed 2 twice). Return the answer modulo $10^9 + 7$.

Why is this asked in interviews?

This problem is asked by companies like Microsoft and Goldman Sachs to test your understanding of Dynamic Programming on strings. It’s a variation of the "Climbing Stairs" or "Ways to Decode" problem. It evaluations your ability to handle variable jump lengths (some keys have 3 letters, some have 4) and aggregate results across a sequence.

Algorithmic pattern used

This is a 1D Dynamic Programming problem.

1. Define dp[i] as the number of ways to decode the prefix of the string of length i.
2. For each position i, look at the previous characters. If they are the same as the current character, you can form a "group".
3. For keys 2-6 and 8, you can group up to 3 identical digits.
4. For keys 7 and 9, you can group up to 4 identical digits.
5. dp[i] = sum(dp[i-k]) for all valid group lengths k.

Example explanation

String: "222" (Key 2 has 3 letters: a, b, c)

• dp[0] = 1 (empty string)
• dp[1] = dp[0] = 1 (message: "a")
• dp[2] = dp[1] + dp[0] = 2 (messages: "aa", "b")
• dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4 (messages: "aaa", "ab", "ba", "c") Total: 4.

Common mistakes candidates make

A common error is not distinguishing between keys that have 3 letters and those that have 4 ('7' and '9'). Another mistake is not applying the modulo at each addition, leading to overflow. Some candidates also forget to check if the sequence of characters is actually identical before summing the previous DP states.

Interview preparation tip

This problem is a great way to practice the "look-back" DP technique. When the number of ways to reach a state depends on a small, fixed number of previous states, an iterative $O(n)$ solution is usually the best approach.