Problem

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 thetotal number of possible text messages Alice could have sent.

Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

Input: pressedKeys = "222222222222222222222222222222222222"
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 10^9 + 7, we return 2082876103 % (10^9 + 7) = 82876089.

Constraints

  • 1 <= pressedKeys.length <= 10^5
  • pressedKeys only consists of digits from '2' - '9'.

Solution

Method 1 – Dynamic Programming with Grouped Key Presses

Intuition

We can use dynamic programming to count the number of ways to decode the pressed keys. For each position, we look back up to 3 or 4 previous positions (depending on the digit) to see if a valid group can be formed, and sum the ways to reach those positions.

Approach

  1. Let dp[i] be the number of ways to decode the first i characters.
  2. Initialize dp[0] = 1 (empty string has one way).
  3. For each position i from 1 to n:
    • For each possible group size (up to 3 for digits 2-6,8, and up to 4 for 7,9), if the last k digits are the same, add dp[i-k] to dp[i].
  4. Return dp[n] modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int countTexts(string pressedKeys) {
        const int MOD = 1e9+7;
        int n = pressedKeys.size();
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i-1];
            for (int k = 2; k <= (pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9' ? 4 : 3); ++k) {
                if (i-k < 0) break;
                bool ok = true;
                for (int j = 1; j < k; ++j) if (pressedKeys[i-j-1] != pressedKeys[i-1]) ok = false;
                if (ok) dp[i] = (dp[i] + dp[i-k]) % MOD;
                else break;
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func CountTexts(pressedKeys string) int {
    MOD := 1_000_000_007
    n := len(pressedKeys)
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        dp[i] = dp[i-1]
        maxK := 3
        if pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9' {
            maxK = 4
        }
        for k := 2; k <= maxK; k++ {
            if i-k < 0 {
                break
            }
            ok := true
            for j := 1; j < k; j++ {
                if pressedKeys[i-j-1] != pressedKeys[i-1] {
                    ok = false
                    break
                }
            }
            if ok {
                dp[i] = (dp[i] + dp[i-k]) % MOD
            } else {
                break
            }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int countTexts(String pressedKeys) {
        int MOD = 1_000_000_007, n = pressedKeys.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i-1];
            int maxK = (pressedKeys.charAt(i-1) == '7' || pressedKeys.charAt(i-1) == '9') ? 4 : 3;
            for (int k = 2; k <= maxK; k++) {
                if (i-k < 0) break;
                boolean ok = true;
                for (int j = 1; j < k; j++) if (pressedKeys.charAt(i-j-1) != pressedKeys.charAt(i-1)) ok = false;
                if (ok) dp[i] = (dp[i] + dp[i-k]) % MOD;
                else break;
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun countTexts(pressedKeys: String): Int {
        val MOD = 1_000_000_007
        val n = pressedKeys.length
        val dp = IntArray(n+1)
        dp[0] = 1
        for (i in 1..n) {
            dp[i] = dp[i-1]
            val maxK = if (pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9') 4 else 3
            for (k in 2..maxK) {
                if (i-k < 0) break
                var ok = true
                for (j in 1 until k) if (pressedKeys[i-j-1] != pressedKeys[i-1]) ok = false
                if (ok) dp[i] = (dp[i] + dp[i-k]) % MOD else break
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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] = dp[i-1]
            maxk = 4 if pressedKeys[i-1] in '79' else 3
            for k in range(2, maxk+1):
                if i-k < 0: break
                if all(pressedKeys[i-j-1] == pressedKeys[i-1] for j in range(1, k)):
                    dp[i] = (dp[i] + dp[i-k]) % MOD
                else:
                    break
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn count_texts(pressed_keys: String) -> i32 {
        let m = 1_000_000_007;
        let n = pressed_keys.len();
        let s = pressed_keys.as_bytes();
        let mut dp = vec![0; n+1];
        dp[0] = 1;
        for i in 1..=n {
            dp[i] = dp[i-1];
            let maxk = if s[i-1] == b'7' || s[i-1] == b'9' { 4 } else { 3 };
            for k in 2..=maxk {
                if i < k { break; }
                if (1..k).all(|j| s[i-j-1] == s[i-1]) {
                    dp[i] = (dp[i] + dp[i-k]) % m;
                } else {
                    break;
                }
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    countTexts(pressedKeys: string): number {
        const MOD = 1_000_000_007;
        const n = pressedKeys.length;
        const dp = new Array(n+1).fill(0);
        dp[0] = 1;
        for (let i = 1; i <= n; i++) {
            dp[i] = dp[i-1];
            const maxK = (pressedKeys[i-1] === '7' || pressedKeys[i-1] === '9') ? 4 : 3;
            for (let k = 2; k <= maxK; k++) {
                if (i-k < 0) break;
                let ok = true;
                for (let j = 1; j < k; j++) if (pressedKeys[i-j-1] !== pressedKeys[i-1]) ok = false;
                if (ok) dp[i] = (dp[i] + dp[i-k]) % MOD;
                else break;
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the pressedKeys string. For each position, we check up to 4 previous positions (constant time per position).
  • 🧺 Space complexity: O(n), for the dp array of size n+1.