# Count Number of Texts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-texts)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-texts
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, String
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
Alice is texting Bob using her phone. The **mapping** of digits to letters is shown in the figure below.

![](https://assets.glich.co/dsa/count-number-of-texts/image0.png) 

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 <= 105`
* `pressedKeys` only consists of digits from `'2'` \- `'9'`.

# Approaches
## Brute-Force Recursion
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.
**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`.
**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.
### Explanation
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:
1.  **One press:** We can always form a character with a single press. We add the result of `count(index + 1)` to our total.
2.  **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 of `count(index + 2)` to our total.
3.  **Three presses:** Similarly, if there are three identical digits, we add `count(index + 3)`.
4.  **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 for `count(index)`. All additions are performed modulo `10^9 + 7`.
This method is straightforward but highly inefficient because it recomputes the same subproblems multiple times. For example, `count(5)` might be called from `count(4)`, `count(3)`, and `count(2)`.

```java
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;
    }
}
```
### Algorithm
- Create a recursive function `solve(index, s)`.
- Base Case: If `index` equals the length of `s`, 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 to `ans`.
- **Case 2 (2 presses):** If `index + 1` is within bounds and `s.charAt(index) == s.charAt(index + 1)`, we can form a letter with two presses. Recursively call `solve(index + 2, s)` and add the result to `ans`.
- **Case 3 (3 presses):** If `index + 2` is within bounds and the three digits from `index` are identical, call `solve(index + 3, s)` and add to `ans`.
- **Case 4 (4 presses):** If the current digit is '7' or '9', `index + 3` is within bounds, and the four digits from `index` are identical, call `solve(index + 4, s)` and add to `ans`.
- Return `ans` modulo `10^9 + 7`.

## Recursion with Memoization (Top-Down DP)
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.
**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.
**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.
### Explanation
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 return `memo[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 to `count` with the same `index` will take constant time.
This technique effectively reduces the time complexity from exponential to linear, as each subproblem `count(index)` is solved only once.

```java
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;
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `n` and initialize it with a sentinel value (e.g., -1).
- Create a recursive function `solve(index, s, memo)`.
- Base Case: If `index` equals the length of `s`, return 1.
- Memoization Check: If `memo[index]` is not -1, return `memo[index]`.
- The rest of the logic is the same as the brute-force approach: calculate the answer `ans` by 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`.

## Iterative Dynamic Programming (Bottom-Up DP)
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.
**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.
**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.
### Explanation
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 = 1` to `n`. For each `i`, we calculate `dp[i]` based on the previous values in the `dp` array.
- The number of ways to decode a prefix of length `i` can 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 is `dp[i-1]`. So, `dp[i]` starts with `dp[i-1]`.
  - If `pressedKeys[i-1]` and `pressedKeys[i-2]` are the same, we can also form a character with the last two presses. We add `dp[i-2]` to `dp[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 is `dp[n]`. This approach avoids recursion and its associated overhead.

```java
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];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`.
- Initialize `dp[0] = 1` (representing one way to decode an empty prefix: the empty message).
- Iterate `i` from 1 to `n`:
  - `dp[i] = dp[i-1]` (for a 1-press character ending at `i-1`).
  - If `i >= 2` and `s.charAt(i-1) == s.charAt(i-2)`, add `dp[i-2]` to `dp[i]`.
  - If `i >= 3` and the last 3 characters are the same, add `dp[i-3]` to `dp[i]`.
  - If `i >= 4`, the character is '7' or '9', and the last 4 characters are the same, add `dp[i-4]` to `dp[i]`.
  - All additions are performed modulo `MOD`.
- The final result is `dp[n]`.

## Space-Optimized Iterative DP
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize four variables to hold the last four DP states: `d0 = 1` (for `dp[i-1]`), `d1 = 0` (for `dp[i-2]`), `d2 = 0` (for `dp[i-3]`), `d3 = 0` (for `dp[i-4]`). The initial `d0=1` corresponds to the base case `dp[0]=1`.
- Iterate `i` from 1 to `n`:
  - Calculate `current_dp` using 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`.
- After the loop, `d0` holds the final result `dp[n]`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans
```