Count Number of Texts

Medium

Goldman Sachs

0 views

Topics:

Dynamic ProgrammingStrings

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

[Image of a phone keypad]

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 10^9 + 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 10^9 + 7, we return 2082876103 % (10^9 + 7) = 82876089.

What are the time and space complexities of your solution? Can you think of any edge cases?

Count Number of Texts

Medium

Goldman Sachs

0 views

Topics:

Dynamic ProgrammingStrings

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

[Image of a phone keypad]

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 10^9 + 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 10^9 + 7, we return 2082876103 % (10^9 + 7) = 82876089.

What are the time and space complexities of your solution? Can you think of any edge cases?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the `pressedKeys` string?
Can the `pressedKeys` string contain characters other than digits 2-9?
If the `pressedKeys` string is empty, what should I return?
Are there any specific keypad mappings I should assume beyond the standard telephone keypad (e.g., '2' maps to 'abc', '3' to 'def', etc.)?
Could you provide a small example to illustrate the expected output for a simple input?

Brute Force Solution

Approach

The brute force method exhaustively explores all possible combinations of text sequences to find the valid ones. We essentially try every possible sequence, validating each against the problem's constraints. If valid, increment a counter, and continue until all sequences have been evaluated.

Here's how the algorithm would work step-by-step:

Consider the input text string and realize that each digit can correspond to a number of different letters (e.g., '2' can be 'a', 'b', or 'c').
Start by considering all possible single-character combinations. For example, if the input is '2', the combinations are 'a', 'b', and 'c'.
Now, consider two-character combinations. If the input is '23', combine each option from '2' (a, b, c) with each option from '3' (d, e, f) resulting in 'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'.
Continue this process for longer input strings, building every possible text sequence.
As you generate each text sequence, check if it is a valid sequence according to what you want to count. (In the original problem statement the goal is to simply count combinations, so all sequences are valid).
For each valid text sequence, increment a counter.
After exploring all possible sequences, the counter will hold the total number of valid text sequences.

Code Implementation

def count_number_of_texts_brute_force(pressed_keys: str) -> int:
    digit_to_letters = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

    number_of_valid_text_sequences = 0

    def generate_combinations(index: int, current_text: str):
        nonlocal number_of_valid_text_sequences

        # Base case: If we've processed all digits
        if index == len(pressed_keys):
            # Increment count when a combination is complete
            number_of_valid_text_sequences += 1
            return

        digit = pressed_keys[index]
        letters = digit_to_letters[digit]

        # Recursive step: Explore letter options for the current digit
        for letter in letters:
            # Explore the next digit
            generate_combinations(index + 1, current_text + letter)

    # Initiate the recursive process starting with an empty combination
    generate_combinations(0, "")
    
    return number_of_valid_text_sequences

Big(O) Analysis

Time Complexity

O(3^n) – Let n be the length of the input string. For each digit, we can have a different number of possibilities: 3 for digits like '2', '3', '4', '5', '6', '8' and 4 for digits '7' and '9'. In the worst case, each digit has 3 possibilities. This leads to exploring all combinations, resulting in 3 choices for each of the n digits. Therefore, the number of possible combinations grows exponentially as 3^n. This dominates the runtime, resulting in a time complexity of O(3^n).

Space Complexity

O(3^N) – The brute force approach, as described, explores all possible text sequences. Since each digit maps to 3 or 4 characters, and we are generating every possible combination, the number of combinations can grow exponentially. In the worst case, if all digits map to 3 characters each, the space required to store these combinations grows proportionally to 3 raised to the power of N, where N is the length of the input string. This is because each digit has 3 possible mappings and we explore all possible combinations of these mappings recursively. Therefore the space complexity is O(3^N).

Optimal Solution

Approach

The optimal way to count the number of texts is to recognize that each digit can represent a limited number of letters. We can use dynamic programming to build up the solution from smaller subproblems. By reusing previous calculations, we avoid recomputing the same counts multiple times.

Here's how the algorithm would work step-by-step:

Create a way to remember the number of ways to form a text up to each point in the sequence of digits.
Start from the beginning of the digits.
For each digit, check how many possible letters it can represent (e.g., 2 represents 'a', 'b', or 'c').
Based on the number of possible letters, look back at previously calculated counts and add them to the current count. This means we're building upon the number of ways to text from earlier parts of the sequence.
Handle special cases like digits that represent four letters (like '7' or '9').
Move one digit forward and repeat the counting and adding until you've reached the end of the digits.
The final number you have represents the total number of possible texts.

Code Implementation

def count_number_of_texts(pressed_keys: str) -> int:
    modulo = 10**9 + 7
    length_of_keys = len(pressed_keys)
    dp_table = [0] * (length_of_keys + 1)

    dp_table[0] = 1

    for i in range(1, length_of_keys + 1):
        # Base case: the last key is always one way to form a text
        dp_table[i] = dp_table[i - 1]

        if i > 1 and pressed_keys[i - 1] == pressed_keys[i - 2]:
            dp_table[i] = (dp_table[i] + dp_table[i - 2]) % modulo

            # If the same key is pressed thrice, add the ways from i-3
            if i > 2 and pressed_keys[i - 1] == pressed_keys[i - 3]:
                dp_table[i] = (dp_table[i] + dp_table[i - 3]) % modulo

                # Handle keys '7' and '9' which can represent four letters
                if (i > 3 and
                        pressed_keys[i - 1] == pressed_keys[i - 4] and
                        (pressed_keys[i - 1] == '7' or pressed_keys[i - 1] == '9')):

                    # Add possibilities for the four letter cases
                    dp_table[i] = (dp_table[i] + dp_table[i - 4]) % modulo

    return dp_table[length_of_keys]

Big(O) Analysis

Time Complexity

O(n) – The dynamic programming approach iterates through the input digits string of length n once. For each digit, it checks a maximum of four previous counts to accumulate the possible texts. Since the number of operations per digit is constant and bounded by a small constant (<=4), the overall time complexity is directly proportional to the length of the input string n, resulting in O(n).

Space Complexity

O(N) – The algorithm uses dynamic programming to remember the number of ways to form a text up to each point in the sequence of digits. This is achieved by creating a data structure, typically an array or list, to store these counts. The size of this array is directly proportional to the number of digits in the input sequence, which we denote as N. Therefore, the auxiliary space used is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input string	Return 1, as an empty string represents one possible (empty) text message.
Null input string	Throw an IllegalArgumentException or return 0, depending on the requirements.
String with a single character	Return the number of letters the digit represents (3 for 2,3,4,5,6,8 and 4 for 7,9).
String with only '1' or '0' characters	Return 1, as '1' and '0' map to themselves and do not contribute to additional text possibilities.
Long string with repeating characters (e.g., '2222222222')	Use dynamic programming to avoid exponential time complexity for long repeating sequences, memoizing the counts.
Input string with mixed valid and invalid characters (e.g., '2a3')	Throw an IllegalArgumentException or filter out invalid characters and process the remaining valid digits only.
Large input string to test performance (stress test)	Ensure dynamic programming solution is efficient enough to handle inputs with length up to 10^5 within time constraints.
Integer overflow during calculation of text message counts	Apply modulo operation (10^9 + 7) after each multiplication and addition to prevent integer overflow.