Count Number of Texts - Solution & Explanation

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.