Alice pressed phone number buttons, each letter maps to 2-4 presses. Count number of possible original messages.
Input: pressedKeys="22233" → Output: 8
Input: pressedKeys="222222222222222222222222222222222222" → Output: 82876089
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
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)