Count Number of Texts
MedPrompt
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 <= 105pressedKeysonly consists of digits from'2'-'9'.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to explore all possible ways of decoding the pressedKeys string. The function tries to form a valid character by taking 1, 2, 3, or (if applicable) 4 identical consecutive digits and recursively calls itself for the rest of the string. The total count is the sum of possibilities from all valid choices.
Algorithm
- Create a recursive function
solve(index, s). - Base Case: If
indexequals the length ofs, return 1, as we've found one valid decoding. - Initialize
ans = 0. - Case 1 (1 press): A single digit can always form a letter. Recursively call
solve(index + 1, s)and add the result toans. - Case 2 (2 presses): If
index + 1is within bounds ands.charAt(index) == s.charAt(index + 1), we can form a letter with two presses. Recursively callsolve(index + 2, s)and add the result toans. - Case 3 (3 presses): If
index + 2is within bounds and the three digits fromindexare identical, callsolve(index + 3, s)and add toans. - Case 4 (4 presses): If the current digit is '7' or '9',
index + 3is within bounds, and the four digits fromindexare identical, callsolve(index + 4, s)and add toans. - Return
ansmodulo10^9 + 7.
Walkthrough
We define a recursive helper function, say count(index), which calculates the number of ways to decode the suffix of the string starting from index.
The base case for the recursion is when index reaches the end of the string (index == pressedKeys.length()), which means we have successfully decoded the entire string. In this case, we return 1.
In the recursive step, for the current index, we explore all possible valid groupings of the current digit:
- One press: We can always form a character with a single press. We add the result of
count(index + 1)to our total. - Two presses: If there are at least two identical digits starting from
index, we can form a character with two presses. We add the result ofcount(index + 2)to our total. - Three presses: Similarly, if there are three identical digits, we add
count(index + 3). - Four presses: If the digit is '7' or '9' and there are four identical digits, we add
count(index + 4). The sum of these possibilities gives the result forcount(index). All additions are performed modulo10^9 + 7. This method is straightforward but highly inefficient because it recomputes the same subproblems multiple times. For example,count(5)might be called fromcount(4),count(3), andcount(2).
class Solution { int MOD = 1_000_000_007; String s; public int countTexts(String pressedKeys) { this.s = pressedKeys; return solve(0); } private int solve(int index) { if (index == s.length()) { return 1; } long ans = 0; char c = s.charAt(index); // 1-press ans = (ans + solve(index + 1)) % MOD; // 2-presses if (index + 1 < s.length() && s.charAt(index + 1) == c) { ans = (ans + solve(index + 2)) % MOD; } else { return (int) ans; } // 3-presses if (index + 2 < s.length() && s.charAt(index + 2) == c) { ans = (ans + solve(index + 3)) % MOD; } else { return (int) ans; } // 4-presses (only for '7' and '9') if ((c == '7' || c == '9') && index + 3 < s.length() && s.charAt(index + 3) == c) { ans = (ans + solve(index + 4)) % MOD; } return (int) ans; }}Complexity
Time
O(4^n), where n is the length of `pressedKeys`. In the worst case, each call can branch up to 4 times, leading to an exponential number of calls.
Space
O(n), for the recursion call stack depth, where n is the length of `pressedKeys`.
Trade-offs
Pros
Simple to understand and implement the logic.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.
This approach improves upon the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use a DP array, memo, to store the results of count(index). Before computing the result for an index, we check if it's already in our memo array. If so, we return the stored value; otherwise, we compute it, store it, and then return it.
Algorithm
- Create a memoization array
memoof sizenand initialize it with a sentinel value (e.g., -1). - Create a recursive function
solve(index, s, memo). - Base Case: If
indexequals the length ofs, return 1. - Memoization Check: If
memo[index]is not -1, returnmemo[index]. - The rest of the logic is the same as the brute-force approach: calculate the answer
ansby summing up the results of recursive calls for 1, 2, 3, or 4-press combinations. - Before returning
ans, store it in the memoization table:memo[index] = ans. - Return
ans.
Walkthrough
This is a classic dynamic programming optimization. The recursive structure remains the same as the brute-force approach. We introduce an array, memo, of the same size as the input string, initialized with a special value (e.g., -1) to indicate that the state has not been computed yet.
The function count(index, memo) works as follows:
- Base Case: If
index == pressedKeys.length(), return 1. - Memoization Check: If
memo[index]is not -1, it means we have already computed the result for this subproblem, so we returnmemo[index]. - Computation: If the result is not memoized, we perform the same calculations as in the brute-force approach, exploring 1, 2, 3, or 4-press options.
- Store and Return: The computed result is stored in
memo[index]before being returned. This ensures that any subsequent call tocountwith the sameindexwill take constant time. This technique effectively reduces the time complexity from exponential to linear, as each subproblemcount(index)is solved only once.
class Solution { int MOD = 1_000_000_007; String s; int[] memo; public int countTexts(String pressedKeys) { this.s = pressedKeys; this.memo = new int[s.length()]; java.util.Arrays.fill(memo, -1); return solve(0); } private int solve(int index) { if (index == s.length()) { return 1; } if (memo[index] != -1) { return memo[index]; } long ans = 0; char c = s.charAt(index); // 1-press ans = (ans + solve(index + 1)) % MOD; // 2-presses if (index + 1 < s.length() && s.charAt(index + 1) == c) { ans = (ans + solve(index + 2)) % MOD; } else { return memo[index] = (int) ans; } // 3-presses if (index + 2 < s.length() && s.charAt(index + 2) == c) { ans = (ans + solve(index + 3)) % MOD; } else { return memo[index] = (int) ans; } // 4-presses (only for '7' and '9') if ((c == '7' || c == '9') && index + 3 < s.length() && s.charAt(index + 3) == c) { ans = (ans + solve(index + 4)) % MOD; } return memo[index] = (int) ans; }}Complexity
Time
O(n). Each state `solve(index)` is computed only once. The work inside each call is constant time.
Space
O(n), for the memoization array and the recursion stack depth.
Trade-offs
Pros
Efficient enough to pass the given constraints.
Logically similar to the brute-force approach, making it relatively easy to transition to.
Cons
Uses O(n) extra space for both the memoization table and the recursion stack.
An iterative approach can avoid the recursion stack overhead, making it slightly more performant in some environments.
This approach converts the top-down memoized recursion into an iterative, bottom-up solution. We use a DP array, dp, where dp[i] stores the number of ways to decode the prefix of pressedKeys of length i. We build up the solution from smaller subproblems to larger ones.
Algorithm
- Create a DP array
dpof sizen + 1. - Initialize
dp[0] = 1(representing one way to decode an empty prefix: the empty message). - Iterate
ifrom 1 ton:dp[i] = dp[i-1](for a 1-press character ending ati-1).- If
i >= 2ands.charAt(i-1) == s.charAt(i-2), adddp[i-2]todp[i]. - If
i >= 3and the last 3 characters are the same, adddp[i-3]todp[i]. - If
i >= 4, the character is '7' or '9', and the last 4 characters are the same, adddp[i-4]todp[i]. - All additions are performed modulo
MOD.
- The final result is
dp[n].
Walkthrough
We create a DP array dp of size n+1, where n is the length of pressedKeys. dp[i] will store the number of possible messages for the prefix pressedKeys[0...i-1].
dp[0]is initialized to 1, representing one way to decode an empty string (the empty message).- We then iterate from
i = 1ton. For eachi, we calculatedp[i]based on the previous values in thedparray. - The number of ways to decode a prefix of length
ican be found by considering the last group of presses. The last group can be of size 1, 2, 3, or 4.- If we form a character with the last press (
pressedKeys[i-1]), the number of ways isdp[i-1]. So,dp[i]starts withdp[i-1]. - If
pressedKeys[i-1]andpressedKeys[i-2]are the same, we can also form a character with the last two presses. We adddp[i-2]todp[i]. - If the last three presses are identical, we add
dp[i-3]. - If the digit is '7' or '9' and the last four presses are identical, we add
dp[i-4]. The final answer isdp[n]. This approach avoids recursion and its associated overhead.
- If we form a character with the last press (
class Solution { public int countTexts(String pressedKeys) { int n = pressedKeys.length(); int MOD = 1_000_000_007; long[] dp = new long[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { char c = pressedKeys.charAt(i - 1); // 1-press dp[i] = dp[i - 1]; // 2-presses if (i >= 2 && pressedKeys.charAt(i - 2) == c) { dp[i] = (dp[i] + dp[i - 2]) % MOD; } // 3-presses if (i >= 3 && pressedKeys.charAt(i - 3) == c && pressedKeys.charAt(i-2) == c) { dp[i] = (dp[i] + dp[i - 3]) % MOD; } // 4-presses (only for '7' and '9') if ((c == '7' || c == '9') && i >= 4 && pressedKeys.charAt(i - 4) == c && pressedKeys.charAt(i-3) == c && pressedKeys.charAt(i-2) == c) { dp[i] = (dp[i] + dp[i - 4]) % MOD; } } return (int) dp[n]; }}Complexity
Time
O(n). We iterate through the string once, and each step involves a constant number of operations.
Space
O(n) for the DP array.
Trade-offs
Pros
Efficient O(n) time complexity.
Avoids recursion overhead, which can make it slightly faster in practice than the memoized approach.
Cons
Requires O(n) extra space, which can be optimized.
This is the most efficient approach. It builds upon the bottom-up DP but observes that the calculation of dp[i] only depends on the last four values (dp[i-1], dp[i-2], dp[i-3], dp[i-4]). Therefore, we don't need to store the entire DP array and can use a few variables to keep track of only the necessary previous states, reducing the space complexity to constant.
Algorithm
- Initialize four variables to hold the last four DP states:
d0 = 1(fordp[i-1]),d1 = 0(fordp[i-2]),d2 = 0(fordp[i-3]),d3 = 0(fordp[i-4]). The initiald0=1corresponds to the base casedp[0]=1. - Iterate
ifrom 1 ton:- Calculate
current_dpusing the four variables, following the same logic as the standard bottom-up DP. current_dp = d0- If the condition for a 2-press character is met,
current_dp = (current_dp + d1) % MOD. - If the condition for a 3-press character is met,
current_dp = (current_dp + d2) % MOD. - If the condition for a 4-press character is met,
current_dp = (current_dp + d3) % MOD. - Update the variables for the next iteration by shifting them:
d3 = d2,d2 = d1,d1 = d0,d0 = current_dp.
- Calculate
- After the loop,
d0holds the final resultdp[n].
Walkthrough
Instead of a full dp array of size n+1, we only need to maintain the last four DP values. Let's call them d0, d1, d2, and d3, which will represent dp[i-1], dp[i-2], dp[i-3], and dp[i-4] respectively during the i-th iteration.
We iterate from i = 1 to n. In each iteration i, we calculate the new dp[i] (let's call it current_dp) using the values from the previous steps.
The recurrence relation is the same:
current_dp = dp[i-1] + dp[i-2] (if applicable) + dp[i-3] (if applicable) + dp[i-4] (if applicable).
After calculating current_dp, we update our state variables for the next iteration: the old dp[i-4] is discarded, dp[i-3] becomes the new dp[i-4], dp[i-2] becomes the new dp[i-3], dp[i-1] becomes the new dp[i-2], and current_dp becomes the new dp[i-1]. This "sliding window" of DP values allows us to compute the result with constant extra space.
class Solution { public int countTexts(String pressedKeys) { int n = pressedKeys.length(); int MOD = 1_000_000_007; // d0 corresponds to dp[i-1], d1 to dp[i-2], etc. long d0 = 1; // Initially for dp[0] long d1 = 0; // Initially for dp[-1] long d2 = 0; // Initially for dp[-2] long d3 = 0; // Initially for dp[-3] for (int i = 1; i <= n; i++) { long current_dp = d0; // From 1-press char c = pressedKeys.charAt(i - 1); if (i >= 2 && c == pressedKeys.charAt(i - 2)) { current_dp = (current_dp + d1) % MOD; // From 2-presses } if (i >= 3 && c == pressedKeys.charAt(i - 2) && c == pressedKeys.charAt(i - 3)) { current_dp = (current_dp + d2) % MOD; // From 3-presses } if ((c == '7' || c == '9') && i >= 4 && c == pressedKeys.charAt(i - 2) && c == pressedKeys.charAt(i - 3) && c == pressedKeys.charAt(i - 4)) { current_dp = (current_dp + d3) % MOD; // From 4-presses } // Shift the window for the next iteration d3 = d2; d2 = d1; d1 = d0; d0 = current_dp; } return (int) d0; }}Complexity
Time
O(n). A single pass through the string is performed.
Space
O(1). We only use a constant number of variables to store the previous DP states.
Trade-offs
Pros
Most optimal solution in terms of both time and space.
Achieves linear time complexity with constant space usage.
Cons
Can be slightly more complex to reason about and implement correctly compared to the standard DP approach.
Solutions
Solution
class Solution {private static final int N = 100010;private static final int MOD = (int)1 e9 + 7;private static long[] f = new long[N];private static long[] g = new long[N]; static { f[0] = 1; f[1] = 1; f[2] = 2; f[3] = 4; g[0] = 1; g[1] = 1; g[2] = 2; g[3] = 4; for (int i = 4; i < N; ++i) { f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD; g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % MOD; } }public int countTexts(String pressedKeys) { long ans = 1; for (int i = 0, n = pressedKeys.length(); i < n; ++i) { int j = i; char c = pressedKeys.charAt(i); for (; j + 1 < n && pressedKeys.charAt(j + 1) == c; ++j) ; int cnt = j - i + 1; ans = c == '7' || c == '9' ? ans * g[cnt] : ans * f[cnt]; ans %= MOD; i = j; } return (int)ans; }}const int mod = 1e9 + 7 ; const int n = 1e5 + 10 ; long long f [ n ], g [ n ]; int init = []() { f [ 0 ] = g [ 0 ] = 1 ; f [ 1 ] = g [ 1 ] = 1 ; f [ 2 ] = g [ 2 ] = 2 ; f [ 3 ] = g [ 3 ] = 4 ; for ( int i = 4 ; i < n ; ++ i ) { f [ i ] = ( f [ i - 1 ] + f [ i - 2 ] + f [ i - 3 ]) % mod ; g [ i ] = ( g [ i - 1 ] + g [ i - 2 ] + g [ i - 3 ] + g [ i - 4 ]) % mod ; } return 0 ; }(); class Solution { public: int countTexts ( string pressedKeys ) { long long ans = 1 ; for ( int i = 0 , n = pressedKeys . length (); i < n ; ++ i ) { char c = pressedKeys [ i ]; int j = i ; while ( j + 1 < n && pressedKeys [ j + 1 ] == c ) { ++ j ; } int cnt = j - i + 1 ; ans = c == '7' || c == '9' ? ans * g [ cnt ] : ans * f [ cnt ]; ans %= mod ; i = j ; } return ans ; } };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 ch , s in groupby ( pressedKeys ): m = len ( list ( s )) ans = ans * ( g [ m ] if ch in "79" else f [ m ]) % mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.