Introduction

In this blog post, we will explore how to solve the LeetCode problem "2266" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below. 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 109 + 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 <= 105 pressedKeys only consists of digits from '2' - '9'.

Explanation

Here's a breakdown of the solution:

• Decompose into Runs: The problem can be broken down into consecutive runs of the same digit. Each run contributes a certain number of possible letter combinations based on the length of the run and the digit itself.
• Count Combinations within Runs: For each run, determine the number of possible letter combinations. This depends on which digit it is and how many letters are mapped to that digit. Digits 2-6 and 8-9 have 3 letters, while digit 7 has 4.

• Multiply and Modulo: The total number of possible messages is the product of the number of combinations from each run. We need to take the modulo after each multiplication to avoid integer overflow.

• Runtime Complexity: O(n) & Storage Complexity: O(1)

Code

    def count_texts(pressedKeys: str) -> int:
    """
    Calculates the total number of possible text messages Alice could have sent,
    given the string of pressed keys received by Bob.

    Args:
        pressedKeys: The string of pressed keys.

    Returns:
        The total number of possible text messages modulo 10^9 + 7.
    """
    MOD = 10**9 + 7
    n = len(pressedKeys)
    ans = 1
    i = 0

    while i < n:
        j = i
        while j < n and pressedKeys[j] == pressedKeys[i]:
            j += 1
        length = j - i
        digit = pressedKeys[i]

        if digit == '7' or digit == '9':
            dp = [0] * (length + 1)
            dp[0] = 1
            for k in range(1, length + 1):
                dp[k] = dp[k - 1]
                if k >= 2:
                    dp[k] = (dp[k] + dp[k - 2]) % MOD
                if k >= 3:
                    dp[k] = (dp[k] + dp[k - 3]) % MOD
                if k >= 4:
                    dp[k] = (dp[k] + dp[k - 4]) % MOD
            ans = (ans * dp[length]) % MOD

        else:
            dp = [0] * (length + 1)
            dp[0] = 1
            for k in range(1, length + 1):
                dp[k] = dp[k - 1]
                if k >= 2:
                    dp[k] = (dp[k] + dp[k - 2]) % MOD
                if k >= 3:
                    dp[k] = (dp[k] + dp[k - 3]) % MOD
            ans = (ans * dp[length]) % MOD

        i = j

    return ans