<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 __init__(self):
        self.three_letters = set(['2','3','4','5','6','8'])
        self.four_letters = set(['7','9'])

        self.three_letter_starting = [1, 2, 4]
        self.four_letter_starting = [1, 2, 4, 8]


    def count_permutations(self, key_val: chr, times_pressed: int) -> int:
        is_3_letter = key_val in self.three_letters
        dp = [0 for i in range(times_pressed)]
        starting_idx = 0

        if is_3_letter:
            for idx, perm in enumerate(self.three_letter_starting):
                if idx < times_pressed:
                    dp[idx] = perm
            starting_idx = 3
        else:
            for idx, perm in enumerate(self.four_letter_starting):
                if idx < times_pressed:
                    dp[idx] = perm
            starting_idx = 4

        
        idx = starting_idx
        while idx < times_pressed:
            dp[idx] = dp[idx-1] + dp[idx-2] + dp[idx-3]
            if not is_3_letter:
                dp[idx] += dp[idx-4]
            idx += 1
        
        return dp[-1]


    def countTexts(self, pressedKeys: str) -> int:

        keys_pressed = len(pressedKeys)
        if keys_pressed == 1:
            return 1

        starting_idx = 0
        current_key_count = 0
        ans_arr = []
        idx = 0
        while idx < keys_pressed:
            if idx == keys_pressed - 1:
                if starting_idx == idx:
                    ans_arr.append(self.count_permutations(pressedKeys[idx], 1))
                else:
                    ans_arr.append(self.count_permutations(pressedKeys[idx], idx - starting_idx + 1))
                break

            if pressedKeys[idx] != pressedKeys[idx + 1]:
                ans_arr.append(self.count_permutations(pressedKeys[idx], idx - starting_idx + 1))
                starting_idx = idx + 1
            idx += 1

        ans = 1
        for item in ans_arr:
            ans *= item
            ans = ans % (10**9+7)
        return ans


# "22233"

# 5

# idx < 4



        # # 4 letter
        # "7"
        # p

        # "77"
        # pp
        # q

        # "777"
        # ppp
        # qp
        # pq
        # r

        # "7777"
        # pppp
        # qpp
        # pqp
        # rp

        # ppq
        # qq

        # pr

        # s





        # ____________
        
        # "2"
        # a

        # "22"
        # b
        # a a

        # "222"
        # b a
        # a a a
        # a b
        # c

        # "2222"

        # [prev ans + single letter]
        # a a a a
        # a b a
        # b a a
        # c a

        # [2 times ago + 2nd letter (b)]
        # b b
        # a a b

        # [3 times ago + single letter]
        # a c

        # "22222"
        # [prev ans + single letter]
        # a a a a a
        # a b a a
        # b a a a
        # c a a
        # b b a
        # a a b a
        # a c a

        # [2 times ago + 2nd letter (b)]
        # b a b
        # a a a b
        # a b b
        # c b

        # [3 times ago + single letter]
        # b c
        # a a c



    










437241