Skip to main content
Talentd

Count Number of Texts - Solution & Explanation

MediumHash TableMathStringDynamic Programming18 min readAsked at: Amazon, Microsoft, Goldman Sachs
Practice this problem

Problem Statement

Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.

  • For example, to add the letter 's', Alice has to press '7' four times. Similarly, to add the letter 'k', Alice has to press '5' twice.
  • Note that the digits '0' and '1' do not map to any letters, so Alice does not use them.

However, due to an error in transmission, Bob did not receive Alice's text message but received a string of pressed keys instead.

  • For example, when Alice sent the message "bob", Bob received the string "2266622".

Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: pressedKeys = "22233"
Output: 8
Explanation:
The possible text messages Alice could have sent are:
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce".
Since there are 8 possible messages, we return 8.

Example 2:

Input: pressedKeys = "222222222222222222222222222222222222"
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.

 

Constraints:

  • 1 <= pressedKeys.length <= 105
  • pressedKeys only consists of digits from '2' - '9'.

Approach Overview

Problem Overview: You receive a string representing digits pressed on a classic phone keypad. Each digit maps to multiple characters (e.g., 2 → abc, 7 → pqrs). Repeated presses of the same digit choose different letters. The task is to count how many valid text messages could produce the given sequence of key presses.

The main constraint comes from the keypad mapping: digits 2,3,4,5,6,8 support at most 3 consecutive presses, while 7 and 9 support up to 4. When you see a run like 2222, you must split it into valid groups where each group length does not exceed the allowed limit. The problem becomes counting how many ways you can partition each run.

Approach 1: Brute Force Backtracking (Exponential Time, O(2^n) worst case)

A straightforward idea is to recursively try every possible grouping of consecutive digits. For each index, attempt to take 1–3 digits (or 1–4 for digits 7 and 9) as long as the digits are identical. Continue exploring all valid splits until reaching the end of the string. This approach mirrors generating all possible message interpretations. However, overlapping subproblems appear quickly, especially for long runs like 7777777. The same suffix gets recomputed many times, leading to exponential time complexity and making this impractical for large inputs.

Approach 2: Dynamic Programming (O(n) time, O(n) space)

The efficient solution uses dynamic programming to reuse results for overlapping suffixes. Define dp[i] as the number of ways to interpret the prefix ending at index i. For each position, extend the current group backward while the digits remain the same and the group length stays within the keypad limit (3 or 4). Add the number of ways from the previous valid position.

For example, if the current digit is 2, you can consider groups of length 1, 2, or 3 consisting of the same digit. If the substring pressedKeys[i-k+1..i] contains identical digits, update dp[i] += dp[i-k]. Digits 7 and 9 allow one extra length option. Apply modulo 1e9 + 7 to avoid overflow.

This approach effectively counts the number of valid partitions for each consecutive run. The algorithm processes the string once and checks only up to four previous positions per index, resulting in linear time. The problem fits naturally into string processing combined with dynamic programming since the number of interpretations depends on previously computed states.

Recommended for interviews: The dynamic programming approach is what interviewers expect. Mentioning the brute force recursion first shows you understand the search space, but recognizing overlapping subproblems and converting it into DP demonstrates strong algorithmic thinking. The final solution runs in O(n) time with O(n) space and handles long key sequences efficiently.

Approach 1: Dynamic Programming Approach

This approach uses a dynamic programming array where dp[i] represents the number of ways to decode the substring pressedKeys[0..i]. We iterate over the string while keeping track of contiguous segments of the same digit. Depending on the digit, the maximum possible number of presses for letters range from 3 to 4. We update our dp array by considering these possible decompositions.

The solution uses a dynamic programming array `dp` where `dp[i]` represents the number of possible messages up to the i-th character. For each position, it checks up to the maximum number of possible key presses (3 or 4) to calculate the combinations possible leading up to that point, leveraging contiguous segments of the same digit. The result at `dp[n]` gives the total combinations for the entire string.

Code

PythonJavaScriptCC++JavaC#

Python

JavaScript

C

C++

Java

C#

Complexity

Time Complexity: O(n), Space Complexity: O(n) where n is the length of the input string.

Try this approach in the editor →

Approach 2: Grouping + Dynamic Programming

According to the problem description, for consecutive identical characters in the string pressedKeys, we can group them together and then calculate the number of ways for each group. Finally, we multiply the number of ways for all groups.

The key problem is how to calculate the number of ways for each group.

If a group of characters is '7' or '9', we can consider the last 1, 2, 3, or 4 characters of the group as one letter, then reduce the size of the group and transform it into a smaller subproblem.

Similarly, if a group of characters is '2', '3', '4', '5', '6', or '8', we can consider the last 1, 2, or 3 characters of the group as one letter, then reduce the size of the group and transform it into a smaller subproblem.

Therefore, we define f[i] to represent the number of ways for a group of length i with identical characters that are not '7' or '9', and g[i] to represent the number of ways for a group of length i with identical characters that are '7' or '9'.

Initially, f[0] = f[1] = 1, f[2] = 2, f[3] = 4, g[0] = g[1] = 1, g[2] = 2, g[3] = 4.

For i \ge 4, we have:

$ \begin{aligned} f[i] & = f[i-1] + f[i-2] + f[i-3] \ g[i] & = g[i-1] + g[i-2] + g[i-3] + g[i-4] \end{aligned}

Finally, we traverse pressedKeys, group consecutive identical characters, calculate the number of ways for each group, and multiply the number of ways for all groups.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string pressedKeys$.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n), Space Complexity: O(n) where n is the length of the input string.

Grouping + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BacktrackingO(2^n) worst caseO(n)Conceptual understanding of all possible keypad groupings; useful for explaining the search space before optimization
Dynamic ProgrammingO(n)O(n)Optimal solution for large inputs; computes valid partitions of digit runs efficiently

Video Solution

Count Number of Texts| Leetcode 2266 | Dynamic Programming| Live coding session • Coding Decoded • 3,795 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Count Number of Texts easy or hard?
Count Number of Texts is rated Medium difficulty. The challenge is recognizing that the problem reduces to counting valid partitions of consecutive digits and applying dynamic programming to avoid exponential recursion.
Count Number of Texts Python/Java solution
Most implementations follow the same DP pattern across languages. Iterate through the string, track consecutive identical digits, and update dp[i] using the previous 1–3 or 1–4 states depending on the digit. The logic translates directly to Python, Java, C++, or JavaScript.
How to solve Count Number of Texts in O(n)?
Iterate through the string and build a DP array where dp[i] represents the number of ways to interpret the prefix ending at i. For each position, look backward up to 3 or 4 characters while digits remain the same. Add the counts from previous valid states and apply modulo 1e9+7.
What is the best approach for Count Number of Texts?
The optimal solution uses dynamic programming. Track the number of ways to interpret the string up to each index and extend groups of identical digits up to length 3 (or 4 for digits 7 and 9). This avoids recomputing overlapping subproblems and runs in O(n) time.
Is Count Number of Texts asked at Google/Amazon/Meta?
Problems involving keypad mappings and dynamic programming on string partitions frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often test DP reasoning, counting combinations, and handling constraints efficiently.
What data structure is used in Count Number of Texts?
The main data structure is a dynamic programming array that stores the number of interpretations up to each index. The solution also relies on string traversal and simple arithmetic operations for counting combinations under modulo.
What is the time complexity of Count Number of Texts?
The optimal dynamic programming solution runs in O(n) time where n is the length of the pressedKeys string. Each index checks at most 3 or 4 previous positions. Space complexity is O(n) for the DP array, though it can be optimized slightly with rolling states.

Ready to solve this problem?

Practice Count Number of Texts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Decode Ways

Next

Letter Combinations of a Phone Number