<p>Alice is texting Bob using her phone. The <strong>mapping</strong> of digits to letters is shown in the figure below.</p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png" style="width: 200px; height: 162px;" />
<p>In order to <strong>add</strong> a letter, Alice has to <strong>press</strong> the key of the corresponding digit <code>i</code> times, where <code>i</code> is the position of the letter in the key.</p>

<ul>
	<li>For example, to add the letter <code>&#39;s&#39;</code>, Alice has to press <code>&#39;7&#39;</code> four times. Similarly, to add the letter <code>&#39;k&#39;</code>, Alice has to press <code>&#39;5&#39;</code> twice.</li>
	<li>Note that the digits <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code> do not map to any letters, so Alice <strong>does not</strong> use them.</li>
</ul>

<p>However, due to an error in transmission, Bob did not receive Alice&#39;s text message but received a <strong>string of pressed keys</strong> instead.</p>

<ul>
	<li>For example, when Alice sent the message <code>&quot;bob&quot;</code>, Bob received the string <code>&quot;2266622&quot;</code>.</li>
</ul>

<p>Given a string <code>pressedKeys</code> representing the string received by Bob, return <em>the <strong>total number of possible text messages</strong> Alice could have sent</em>.</p>

<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> pressedKeys = &quot;22233&quot;
<strong>Output:</strong> 8
<strong>Explanation:</strong>
The possible text messages Alice could have sent are:
&quot;aaadd&quot;, &quot;abdd&quot;, &quot;badd&quot;, &quot;cdd&quot;, &quot;aaae&quot;, &quot;abe&quot;, &quot;bae&quot;, and &quot;ce&quot;.
Since there are 8 possible messages, we return 8.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pressedKeys = &quot;222222222222222222222222222222222222&quot;
<strong>Output:</strong> 82876089
<strong>Explanation:</strong>
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 10<sup>9</sup> + 7, we return 2082876103 % (10<sup>9</sup> + 7) = 82876089.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= pressedKeys.length &lt;= 10<sup>5</sup></code></li>
	<li><code>pressedKeys</code> only consists of digits from <code>&#39;2&#39;</code> - <code>&#39;9&#39;</code>.</li>
</ul>

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        # all possible ways to split up pressedKeys such that
        # each component of the partition can still be mapped to valid letters

        # 2. 2. 2. 3.  3

        # brute force
        # a. 2|2233
        # b. 22| 233
        # c. 222 | 33

        # a.1 2|2|233   a.2 2|22|33

        # repeated work

        # dp/memoization
        # dp
        #      2.  2. 2. 3.  3.  ""
        #dp    8   4  2  2   1   1
        # dp[i] = # ways to decode s[i:]
        # dp[i] initialized to 0
        # Look at s[i], valid standalone
        # dp[i] += dp[i+1] --> # ways to split up s[i:] and then just append s[i] to the beginning of the partition
            # e.g. ____312
            # s[i] = 3
            # dp[i+1] = 2
            # dp[i] = dp[i+2] = 2
        # We also need to check s[i:i+2], s[i:i+3], up to s[i:i+maxTime[s[i]]]
        # and increment count accordingly dp[i] = dp[i:i+k], where k can go from 2 to maxTime[s[i]] if s[i:i+maxTime[s[i]]] can be regarded as a valid component in the partition

        # dict to store up to how many times is it valid to press certain key
        maxTime = {2:3, 3:3, 4:3, 5:3, 6:3, 7:4, 8:3, 9:4}

        n = len(pressedKeys)
        dp = [0]*(n+1)
        dp[n] = 1
        for i in range(n-1,-1,-1):
            c = pressedKeys[i]
            dp[i] = dp[i+1]
            # to see if we can extend to the right and make more valid components for the partition
            for r in range(i+1,min(n, i+maxTime[int(c)])):
                if pressedKeys[r]==c:
                    # can extent
                    dp[i] += dp[r+1]
                else:
                    break
        return dp[0]%(10**9+7)
2096