<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:
    max_seq = {
        "2": 3,
        "3": 3,
        "4": 3,
        "5": 3,
        "6": 3,
        "7": 4,
        "8": 3,
        "9": 4,
    }

    def countTexts(self, pressedKeys: str) -> int:
        """
        - Each consecutive instance of the same number could be processed separately, or 
          as part of a group of 2-4, depending on key
        - If we consider just the first char, it could be processed one way
        - If we then consider the first two chars, we could process num of ways to process
          first char, plus, num of ways to process second char, plus num of ways to process
          both as a group
        - Considering 3 chars, same as number of ways to process 2 chars, plus number of ways
          to process the third char, plus number of ways to process all 3 at once

        777733
        7      | 1
        77     | 2
        777    | 4
        7777   | 8
        77773  | 8
        777733 | 16

        234
        2   | 1
        23  | 1
        234 | 1

        2222
        - 2,2,2,2
        - 22,2,2 | 2,22,2 | 2,2,22
        - 22,22
        - 222,2 | 2,222

        22222
        - 2,2,2,2,2
        - 22,2,2,2 | 2,22,2,2 | 2,2,22,2 | 2,2,2,22
        - 22,22,2 | 22,2,22 | 2,22,22
        - 222,22 | 22,222
        - 222,2,2 | 2,222,2 | 2,2,222

        First-blush: O(n) CC ; O(1) MC
        - If only one key, return 1
        - init left and right pointers to 0
        - init n = 1
        - Loop while right < len(pressedKeys):
            - increment right while pressedKeys[left] == pressedKeys[right]
            - n *= 2^(right - left - 1)
            - set left = right

        DFS w/cache: O(n) — only look at each index once w/memo CC | O(n) MC
        - init a cache dict keyed with key indexes, value is num of combos from there
        - create helper which takes an index, keys str, and the cache
        - if index in cache, return cache[index]
        - if index == len(keysPressed) return 1
        - init a right pointer = index
        - init n = 0
        - while keys[right] == keys[left] and r-l < max_seq[keys[l]]:
            - n += helper(r+1, keys, cache)
        - cache[i] = n
        - return cache[i]

        Bottoms-up DP:
        - Init a prev list of len 4, with 1s
        - init trailing_seq len = 0
        - iterate over pressedKeys
        - Set curr_val = prev[-1]
        - if i > 0 and keys[i-1] == keys[i] and trailing_seq < 3 
          or trailing_seq == 3 and key in 7,9
            - trailing_seq += 1
            - curr_val *= 2^(trailing_seq - 1)
        - else:
            - trailing_seq = 1
        """
        if len(pressedKeys) < 2:
            return len(pressedKeys)

        trail_seq_len = 1
        prev = [1 for i in range(4)]
        keys = pressedKeys
        for i in range(1, len(keys)):
            curr_val = prev[-1]
            if keys[i-1] == keys[i]:
                if keys[i] == "7" or keys[i] == "9":
                    if trail_seq_len < 4:
                        trail_seq_len += 1
                elif trail_seq_len < 3:
                    trail_seq_len += 1

                for j in range(2, 3 - trail_seq_len, -1):
                    curr_val += prev[j]
            else:
                trail_seq_len = 1

            prev = prev[1:] + [curr_val]
        
        n = prev[-1]

        # cache: dict[int,int] = {}
        # n = self.count_vars(0, pressedKeys, cache)

        return n % (10**9 + 7)

    def count_vars(self, i: int, keys: str, cache: dict[int,int]):
        if i in cache:
            return cache[i]
        elif i == len(keys):
            return 1

        r = i
        n = 0
        while (
            r < len(keys) 
            and keys[r] == keys[i] 
            and r-i < self.max_seq[keys[i]]
        ):
            n += self.count_vars(r+1, keys, cache)
            r += 1

        cache[i] = n
        return cache[i]
1773