We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Texts

Number: 2348

Difficulty: Medium

Paid? No

Companies: Amazon, Goldman Sachs

Problem Description

Alice sends a text by repeatedly pressing a digit on her phone, where the number of presses determines which letter is added. However, due to a transmission error, Bob only receives the string of pressed keys. Given the received string, determine the total number of possible text messages Alice could have originally sent. The answer should be computed modulo 10^9 + 7.

Key Insights

  • The pressedKeys string can be split into groups of consecutive identical digits.
  • For each group, the digit maps to letters with a maximum number of allowed presses (3 for digits 2, 3, 4, 5, 6, 8 and 4 for digits 7 and 9).
  • The problem for each group can be viewed as counting the number of ways to partition the group length into parts of size at most maxPress (using dynamic programming).
  • The final answer is the product of the number of interpretations for each group, taken modulo 10^9 + 7.

Space and Time Complexity

Time Complexity: O(n) where n is the length of pressedKeys
Space Complexity: O(n) in worst-case due to DP array; however, since each group is processed separately, the extra space is limited to the maximum size of any group.

Solution

We process the input string to identify contiguous groups of the same digit. For each group, we determine the maximum number of key presses allowed based on the digit (3 for most, 4 for '7' and '9'). Then, we use a dynamic programming approach to calculate the number of ways to partition the group length into valid sequences of key presses. In the DP, dp[i] represents the number of ways the first i presses can be decoded. The recurrence is based on summing dp values for the previous positions (up to the maximum allowed presses). The final answer is obtained by taking the product of the counts for all groups with modulo arithmetic applied throughout.

Code Solutions

MOD = 10**9 + 7

def countTexts(pressedKeys: str) -> int:
    n = len(pressedKeys)
    result = 1
    i = 0
    while i < n:
        # Identify contiguous block of same digit.
        j = i
        while j < n and pressedKeys[j] == pressedKeys[i]:
            j += 1
        # Length of this group.
        count = j - i
        # Determine maximum allowed group length (allowed presses per letter).
        digit = pressedKeys[i]
        if digit in "79":
            maxPress = 4
        else:
            maxPress = 3

        # dp[k] will be number of ways to split k presses for current group.
        dp = [0] * (count + 1)
        dp[0] = 1  # Base case: 0 key presses.
        for pos in range(1, count + 1):
            # For each possible partition, take sum from last maxPress states.
            for k in range(1, maxPress + 1):
                if pos - k >= 0:
                    dp[pos] += dp[pos - k]
                    dp[pos] %= MOD
        # Multiply result by dp[count] for the current group.
        result = (result * dp[count]) % MOD
        i = j
    return result

# Example usage:
print(countTexts("22233"))  # Expected output: 8
← Back to All Questions