Use state transition dynamic programming to quickly compute the number of texts corresponding to the pressed keys. For each substring of repeated digits, count all valid combinations based on the key mapping. Apply modulo arithmetic to handle large outputs and avoid overflow.
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
How GhostInterview Helps
- Provides clear DP templates specific to repeated digit sequences
- Automatically tracks modulo computations to prevent overflow errors
- Guides through block-based counting to match the key-to-letter mapping pattern
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Count Number of Texts instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count Number of Texts from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Calculate the total appeal of all substrings by counting distinct characters efficiently using state transition DP and hash tracking.
Open problem page#3335 Total Characters in String After Transformations ICalculate the total number of characters in a string after repeated transformations using dynamic programming and frequency tracking.
Open problem page#3337 Total Characters in String After Transformations IICalculate the length of a string after repeated transformations using state transition dynamic programming for large t values efficiently.
Open problem page