Count Number of Texts

Share

Alice pressed phone number buttons, each letter maps to 2-4 presses. Count number of possible original messages.

Example 1
Input: pressedKeys="22233" → Output: 8
Example 2
Input: pressedKeys="222222222222222222222222222222222222" → Output: 82876089

Solution Approach

DP: for each group of same digit, count ways to split it (2 or 3 letters per digit depending on key).

  • Count consecutive same digits as runs
  • For digit 7 or 9: up to 4 presses per letter, others up to 3
  • For run of length n: dp[i] = dp[i-1] + dp[i-2] (+ dp[i-3] if 3-press, + dp[i-4] if 4-press)
  • Multiply results for each run with MOD
Java
public int countTexts(String pressedKeys) {
    long MOD = 1_000_000_007L;
    long result = 1;
    int i = 0, n = pressedKeys.length();
    while (i < n) {
        char c = pressedKeys.charAt(i);
        int j = i;
        while (j < n && pressedKeys.charAt(j) == c) j++;
        int len = j - i;
        int maxPress = (c == '7' || c == '9') ? 4 : 3;
        long[] dp = new long[len + 1];
        dp[0] = 1;
        for (int k = 1; k <= len; k++) {
            dp[k] = dp[k-1];
            if (k >= 2) dp[k] = (dp[k] + dp[k-2]) % MOD;
            if (k >= 3) dp[k] = (dp[k] + dp[k-3]) % MOD;
            if (maxPress == 4 && k >= 4) dp[k] = (dp[k] + dp[k-4]) % MOD;
        }
        result = result * dp[len] % MOD;
        i = j;
    }
    return (int) result;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)