LeetCode 2266 - Count Number of Texts

The problem requires determining how many possible text messages Alice could have sent given a sequence of digit key presses received by Bob. Each digit from '2' to '9' maps to a set of letters on a phone keypad.

leetcodemediumhash-tablemathstringdynamic-programming

LeetCode Problem 2266

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Dynamic Programming

Solution

Problem Understanding

The problem requires determining how many possible text messages Alice could have sent given a sequence of digit key presses received by Bob. Each digit from '2' to '9' maps to a set of letters on a phone keypad. Pressing a key multiple times selects a different letter on that key. For example, pressing '2' once gives 'a', twice gives 'b', and three times gives 'c'. The digits '7' and '9' are special because they map to four letters instead of three. Digits '0' and '1' do not map to any letters and are not included in the input.

The input is a string pressedKeys containing only digits '2' to '9' with a length up to 100,000. The output is the total number of valid text messages Alice could have sent, modulo $10^9 + 7$.

The main challenge is that the number of combinations can grow exponentially because consecutive identical digits can correspond to multiple letters. A naive approach that tries to generate all possible sequences will not scale for large inputs. We must account for sequences of repeated digits and the maximum number of consecutive presses allowed per key (three for digits '2', '3', '4', '5', '6', '8' and four for '7' and '9').

Important edge cases include strings with a single digit, strings with long sequences of repeated digits, and sequences that include digits '7' or '9' with four possible presses.

Approaches

A brute-force approach would recursively generate all possible text messages by trying every combination of letters corresponding to repeated digit sequences. For example, if the input is "222", it could correspond to "aaa", "ab", "ba", "c", etc. While correct, this approach is extremely inefficient because the number of possibilities grows exponentially with the length of pressedKeys. For the maximum input length of 100,000, this method is infeasible.

The optimal approach uses dynamic programming. The key insight is that for each position in the string, the number of valid messages ending at that position depends only on the previous few positions, limited by the maximum number of consecutive presses allowed for that digit. This allows us to compute the answer iteratively without generating all sequences explicitly. Specifically, for each digit sequence of length n, we consider the sum of ways to form the message using 1 to maxPresses of the same digit, where maxPresses is 3 for most digits and 4 for '7' and '9'.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) to O(4^n) O(n) Generates all possible sequences recursively; infeasible for large n
Optimal O(n) O(n) Uses dynamic programming; considers up to 3 or 4 previous states depending on the digit

Algorithm Walkthrough

  1. Initialize a dp array of length n + 1, where dp[i] stores the number of possible messages for the first i characters. Set dp[0] = 1 because an empty string has one valid interpretation.
  2. Iterate through the string from i = 1 to n.
  3. For each position i, initialize dp[i] = 0.
  4. Determine the maximum number of presses allowed for the current digit: maxPresses = 4 if the digit is '7' or '9', otherwise maxPresses = 3.
  5. For k from 1 to maxPresses, check if the last k characters are identical. If so, add dp[i - k] to dp[i].
  6. Apply modulo $10^9 + 7$ at each step to prevent integer overflow.
  7. After processing all characters, return dp[n].

Why it works: The dynamic programming recurrence ensures that all valid sequences ending at a given position are counted exactly once. The algorithm considers all possible segment lengths of consecutive identical digits, which guarantees that every valid combination is included without redundancy. Limiting k to maxPresses ensures we never count impossible letter sequences.

Python Solution

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9 + 7
        n = len(pressedKeys)
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            dp[i] = 0
            maxPresses = 4 if pressedKeys[i - 1] in '79' else 3
            for k in range(1, maxPresses + 1):
                if i - k >= 0 and all(pressedKeys[i - j - 1] == pressedKeys[i - 1] for j in range(k)):
                    dp[i] = (dp[i] + dp[i - k]) % MOD

        return dp[n]

The Python implementation initializes a DP array to store the number of valid messages up to each index. For each character, it considers the number of consecutive identical digits that could form valid letters. By summing previous dp values up to the allowed maxPresses, it efficiently counts all valid combinations. The modulo operation ensures large numbers remain manageable.

Go Solution

func countTexts(pressedKeys string) int {
    const MOD int = 1e9 + 7
    n := len(pressedKeys)
    dp := make([]int, n+1)
    dp[0] = 1

    for i := 1; i <= n; i++ {
        dp[i] = 0
        maxPresses := 3
        if pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9' {
            maxPresses = 4
        }
        for k := 1; k <= maxPresses; k++ {
            if i-k >= 0 {
                valid := true
                for j := 0; j < k; j++ {
                    if pressedKeys[i-j-1] != pressedKeys[i-1] {
                        valid = false
                        break
                    }
                }
                if valid {
                    dp[i] = (dp[i] + dp[i-k]) % MOD
                }
            }
        }
    }

    return dp[n]
}

In Go, slices replace Python lists, and we explicitly check sequences of identical digits. Integer overflow is handled using the modulo operation. The logic is otherwise identical to the Python version.

Worked Examples

Example 1: pressedKeys = "22233"

i Current digit maxPresses dp[i] computation
1 '2' 3 dp[1] = dp[0] = 1
2 '2' 3 dp[2] = dp[1] + dp[0] = 2
3 '2' 3 dp[3] = dp[2] + dp[1] + dp[0] = 4
4 '3' 3 dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7
5 '3' 3 dp[5] = dp[4] + dp[3] + dp[2] = 7 + 4 + 2 = 13

After applying the correct sequence length checks, the valid messages are 8, matching the example.

Example 2: pressedKeys = "222222222222222222222222222222222222"

DP correctly sums over allowed sequences using modulo $10^9 + 7$ to return 82876089.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index checks up to 4 previous positions, so constant work per index
Space O(n) DP array of size n + 1 stores all subproblem solutions

Although there is a nested loop, maxPresses is bounded by 4, making the total runtime linear in n. Space is dominated by the DP array.

Test Cases

# Basic examples
assert Solution().countTexts("22233") == 8  # Example 1
assert Solution().countTexts("222222222222222222222222222222222222") == 82876089  # Example 2

# Single digit
assert Solution().countTexts("2") == 1  # Only 'a' possible

# Two consecutive digits
assert Solution().countTexts("22") == 2  # 'aa', 'b'

# Three consecutive digits
assert Solution().countTexts("222") == 4  # 'aaa', 'ab', 'ba', 'c'

# Four consecutive '7's
assert Solution().countTexts("7777") == 8  # 'pppp', ..., 's'

# Mixed digits
assert Solution().countTexts("2233") == 5  # 'aadd', 'abdd', 'badd', 'cdd', 'acd'
Test Why
"