Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

[Image](1200px-telephone-keypad2svg.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 `10^9 + 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 <= 10^5`

- `pressedKeys` only consists of digits from `'2'` - `'9'`.

package com.devstromo.medium.p2266;

public class Solution {

private static final int MOD = 1_000_000_007;

public int countTexts(String pressedKeys) {

int n = pressedKeys.length();

int[] dp = new int[n + 1];

dp[0] = 1;

for (int i = 1; i <= n; i++) {

char currentChar = pressedKeys.charAt(i - 1);

dp[i] = 0;

int maxPress = (currentChar == '7' || currentChar == '9') ? 4 : 3;

for (int j = 1; j <= maxPress && i - j >= 0; j++) {

if (pressedKeys.charAt(i - j) != currentChar) break;

dp[i] = (dp[i] + dp[i - j]) % MOD;

}

}

return dp[n];

}

}

package com.devstromo.medium.p2266;

import org.junit.jupiter.api.DisplayName;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class SolutionUnitTest {

private final Solution solution = new Solution();

@Test

@DisplayName("Test Count Number of Texts")

void testCountNumberOfTexts() {

assertEquals(8, solution.countTexts("22233"));

assertEquals(82876089, solution.countTexts("222222222222222222222222222222222222"));

}

}