<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 number_possible_strings(n_alphabets, max_repeat):
        # Return the number of possible strings that can be represented by some digit
        # which is repeated max_repeat times. n_alphabet is the number of alphabets represented by 
        # that digit. so n_alphabets for 2-8 is 3 and n_alphabets for 9 is 4
        # Since we need to cache the result the entire array used as dynamic programming table 
        # will be returned instead of just the result of number of possible strings max_repeat
        # from 1 repetition to max_repeat
        dp = [1, 1] # 0 repetiitons 0 possible strings
        for i in range(2, max_repeat+1): # for string repeated 1 time to to max_repeat times
            # n_possible = ((1 * repeat[i-1]) times + 1 * repeat[i-2] times + ... 1 * repeat[i-n_alphabets] times) 
            n_possible = 0
            for j in range(min(i, n_alphabets)):
                n_possible = (n_possible + dp[i-j-1]) % 1000000007
            dp.append(n_possible) # keep only the modulo
        return dp


    def countTexts(self, pressedKeys: str) -> int:      
        i,start=0,0    
        repeat_sections = [] # Identify the segments of string in uniformly repeating strings      
        while i < len(pressedKeys):
            if pressedKeys[i] != pressedKeys[start]:
                repeat_sections.append((pressedKeys[start],start,i))
                start = i
            i = i+1
        # End of loop count repeat
        repeat_sections.append((pressedKeys[start], start, i))
        print(repeat_sections)
        # Find the maximal number of repetitions of a single digit for both 3 alphabet and 4 alphabet
        # digits so that we  can build dp_table for both of them
        max_repeat_3, max_repeat_4 = 0,0
        for (digit, start, end) in repeat_sections:
            if digit == '9' or digit == '7':
                if end - start > max_repeat_4:
                    max_repeat_4 = end - start
            else:
                if end - start > max_repeat_3:
                    max_repeat_3 = end - start
        # Now build the dp_table for maximum number of repetitions for both 3 alphabet and 4 alphabet digits
        digit_possibilities_3 = Solution.number_possible_strings(3, max_repeat_3)
        # print(digit_possibilities_3)
        digit_possibilities_4 = Solution.number_possible_strings(4, max_repeat_4)
        # print(digit_possibilities_4)
        # Now go back to repeated sections and multiply the results together
        result = 1
        for (digit, start, end) in repeat_sections:
            if digit == '9' or digit == '7':
                result = (result * digit_possibilities_4[end-start]) % 1000000007
            else:
                result = (result * digit_possibilities_3[end-start]) % 1000000007
        return result
184