#2266

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Number of Texts

Calculate the total number of possible original texts from a pressed key sequence using state transition dynamic programming efficiently.

hash table math string dynamic programming

Problem Statement

Alice is sending messages using her phone keypad, where each digit corresponds to multiple letters. Each letter requires pressing the key a number of times equal to its position on the key.

Due to transmission errors, Bob only received a string of pressed keys instead of the actual message. Compute the total number of possible original text messages that could generate the given sequence.

Examples

Example 1

Input: pressedKeys = "22233"

Output: 8

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

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

Solution Approach

Identify contiguous digit blocks

Scan the pressedKeys string and group consecutive identical digits. Each block represents multiple ways to interpret the letters based on the key mapping.

Apply state transition dynamic programming

Use DP to track the number of ways to decode each block. For a block of length n, sum the possibilities for 1 to maxPress letters, depending on the key's number of letters.

Modulo and aggregation

Since the count can be very large, apply modulo 10^9 + 7 after each calculation. Multiply the results across all blocks to get the total number of texts.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of pressedKeys, as each character is processed once in DP. Space complexity is O(n) for storing DP results for each position, optimized to O(1) if only the last few DP states are kept due to the maxPress limit per key.

What Interviewers Usually Probe

Expect a DP solution based on repeated digits substrings
Check if candidate handles different key lengths (3 or 4 letters per digit)
Look for modulo arithmetic to prevent integer overflow

Common Pitfalls or Variants

Common pitfalls

Miscounting combinations for blocks exceeding key letter limits
Ignoring modulo arithmetic and risking overflow
Treating each digit independently instead of considering contiguous blocks

Follow-up variants

Modify the mapping to allow variable letters per key dynamically
Count texts with additional constraints like maximum word length
Compute all possible message strings explicitly for small pressedKeys

FAQ

What is the main pattern in Count Number of Texts?

The main pattern is state transition dynamic programming applied to contiguous blocks of identical digits.

How do you handle keys with 3 or 4 letters?

Use the maximum number of presses allowed per key in your DP calculation to sum valid text combinations.

Why use modulo 10^9 + 7 in this problem?

Because the number of possible texts can grow very large, and modulo prevents integer overflow.

Can this approach work for pressedKeys up to length 10^5?

Yes, the DP with block optimization ensures linear time processing suitable for large inputs.

Is it necessary to generate all text messages?

No, only counting the number of possible messages is needed; generating each message is inefficient for long sequences.

terminal

Solution

Solution 1: Grouping + Dynamic Programming

According to the problem description, for consecutive identical characters in the string $\textit{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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

mod = 10**9 + 7
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(100000):
    f.append((f[-1] + f[-2] + f[-3]) % mod)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)


class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for c, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if c in "79" else f[m]) % mod
        return ans

Continue Practicing

#2262 total appeal of a string #3335 total characters in string after transformations i #3337 total characters in string after transformations ii