Count Number of Texts - Practice Coding Problems

Count Number of Texts - Problem

Alice is texting Bob using her phone. The mapping of digits to letters is shown below:

Digit to Letter Mapping:

2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

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: 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: pressedKeys = "22"

› Output: 2

💡 Note: Two ways to decode "22": 1) Press '2' once for 'a', then '2' once for 'a' → "aa", 2) Press '2' twice for 'b' → "b"

Example 2 — Multiple Digits

$ Input: pressedKeys = "222"

› Output: 3

💡 Note: Three ways: 1) "aaa" (2+2+2), 2) "ab" (2+22), 3) "ba" (22+2). Cannot use 222 as '2' key has only 3 letters (abc)

Example 3 — Different Digits

$ Input: pressedKeys = "23"

› Output: 2

💡 Note: Two ways: 1) "ad" (2+3), 2) "ae" (2+3). Note: cannot combine different digits like "23"

Constraints

1 ≤ pressedKeys.length ≤ 10⁵
pressedKeys consists of digits ["2", "9"]
pressedKeys only contains valid phone keypad digits

Visualization

Tap to expand

Understanding the Visualization

Input

Pressed keys string from transmission

Process

Find all valid ways to group consecutive same digits

Output

Total count of possible original messages

Key Takeaway

🎯 Key Insight: Count valid ways to split consecutive same digits based on phone key letter counts

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is recognizing this as a decode ways problem where we count valid ways to split consecutive same digits. Best approach uses dynamic programming to build solution bottom-up. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(4ⁿ)	O(n)	Try all possible ways to split the pressed keys into valid letters
Dynamic Programming (Bottom-Up)	O(n)	O(n)	Build solution iteratively from the end using 1D DP array
Memoized Recursion	O(n)	O(n)	Cache results of subproblems to avoid redundant calculations

Recursive Brute Force — Algorithm Steps

Start from beginning of string
For current digit, try all valid lengths (1-4 based on digit)
Recursively solve for remaining substring
Sum all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at first digit and try all valid lengths

Branch

For each valid length, recursively solve remaining string

Sum

Add up all valid combinations

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 1000000007

int getValidLength(char digit) {
    switch(digit) {
        case '2': case '3': case '4': case '5': case '6': case '8': return 3;
        case '7': case '9': return 4;
        default: return 0;
    }
}

int backtrack(char* s, int index, int n) {
    if (index == n) return 1;
    
    char digit = s[index];
    int maxLen = getValidLength(digit);
    if (maxLen == 0) return 0;
    
    long long count = 0;
    
    for (int length = 1; length <= maxLen && index + length <= n; length++) {
        int valid = 1;
        for (int i = index; i < index + length; i++) {
            if (s[i] != digit) {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            count = (count + backtrack(s, index + length, n)) % MOD;
        } else {
            break;
        }
    }
    
    return (int) count;
}

int solution(char* pressedKeys) {
    return backtrack(pressedKeys, 0, strlen(pressedKeys));
}

int main() {
    char pressedKeys[100001];
    fgets(pressedKeys, sizeof(pressedKeys), stdin);
    pressedKeys[strcspn(pressedKeys, "\n")] = 0;
    
    int result = solution(pressedKeys);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4ⁿ)

At each position, we try up to 4 choices, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth is at most n levels deep

⚡ Linearithmic Space

85.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler