Multi-tap keypad: every string a press sequence can spell

Question: Multi-tap keypad: every string a press sequence can spell

Companies: Microsoft, Meta

Difficulty: Medium

Problem statement

An old phone types letters by multi-tap: pressing a key once gives its first letter, twice in a row gives its second letter, and so on. Use this keypad:

You get a string digits of key presses, with no pauses recorded. A run of the same digit is ambiguous: it can be cut into groups in any way, and a group of k presses means the k-th letter of that key. A group can never be longer than the number of letters on its key (no wrap-around), and a group never spans two different digits.

Implement keypad_combinations(digits: str) -> list[str] that returns every string the presses could spell, in sorted order.

Constraints

• 0 <= len(digits) <= 20, each character is 0-9.
• Return [] for an empty input. Raise an error for any other character.

Example 1

input:  "111"
output: ["AAA", "AB", "BA", "C"]

The run of three 1s can be cut as 1+1+1, 1+2, 2+1 or 3.

Example 2

input:  "772"
output: ["SSD", "TD"]

Key 7 has two letters, so its run gives SS or T; the single 2 gives D.

Part 2: return only the number of possible strings for inputs up to 10^5 presses, modulo 10^9 + 7.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

The input is a multi-tap key sequence. A run of the same digit can be cut into
groups in several ways, and each group of k presses picks the k-th letter
on that key. So the task is: list every way to cut every run, and spell each
cut.

Two observations make it simple.

1. Runs are independent. Two different digits never share a letter, so the
   letters for one run never affect the next run. The answer is the Cartesian
   product of the per-run options, in order.
2. No duplicates arise. Inside one run, a different cut gives a different
   letter sequence, because each letter names its group size. Across runs the
   letter sets are disjoint. So we never need a set to remove repeats.

Brute force. Try every subset of "cut / no cut" positions between adjacent
equal digits (2^(n-1) choices), reject cuts that make a group longer than the
key allows, and spell the rest. That is correct but wastes work on invalid
cuts and repeats the spelling for shared prefixes.

Backtracking (what we write). Walk the string with an index i. At i,
look at how many copies of digits[i] follow (run). Try every group size
k from 1 to min(run, len(letters)), append letter k-1, and recurse from
i + k. When i reaches the end, the path is one answer. Every branch we take
is valid, so the work is proportional to the output size.

Counting without listing. The number of answers can be exponential. If
only the count is needed, a DP does it in linear time:
ways[i] = sum(ways[i + k]) for each valid group size k starting at i.
Interviewers often ask for this as part 2.

Invariants.

• path always spells exactly digits[:i].
• A group never crosses a digit boundary and never exceeds the key's letter
  count.

Code

from typing import Dict, List

KEYPAD: Dict[str, str] = {
    "1": "ABC", "2": "DEF", "3": "GHI", "4": "JKL", "5": "MNO",
    "6": "PQR", "7": "ST", "8": "UVW", "9": "XY", "0": "Z",
}


def keypad_combinations(digits: str, keypad: Dict[str, str] = KEYPAD) -> List[str]:
    """Return every string the multi-tap press sequence can spell, sorted."""
    for d in digits:
        if d not in keypad:
            raise ValueError(f"unknown key: {d!r}")
    if not digits:
        return []

    n = len(digits)
    # run_len[i] = how many copies of digits[i] start at position i.
    run_len = [1] * n
    for i in range(n - 2, -1, -1):
        if digits[i] == digits[i + 1]:
            run_len[i] = run_len[i + 1] + 1

    results: List[str] = []
    path: List[str] = []

    def backtrack(i: int) -> None:
        if i == n:
            results.append("".join(path))
            return
        letters = keypad[digits[i]]
        for k in range(1, min(run_len[i], len(letters)) + 1):
            path.append(letters[k - 1])
            backtrack(i + k)
            path.pop()

    backtrack(0)
    results.sort()
    return results


def count_combinations(digits: str, keypad: Dict[str, str] = KEYPAD) -> int:
    """Count the strings without building them. O(n * max_letters)."""
    if not digits:
        return 0
    n = len(digits)
    run_len = [1] * n
    for i in range(n - 2, -1, -1):
        if digits[i] == digits[i + 1]:
            run_len[i] = run_len[i + 1] + 1
    ways = [0] * (n + 1)
    ways[n] = 1
    for i in range(n - 1, -1, -1):
        limit = min(run_len[i], len(keypad[digits[i]]))
        ways[i] = sum(ways[i + k] for k in range(1, limit + 1))
    return ways[0]


if __name__ == "__main__":
    assert keypad_combinations("") == []
    assert keypad_combinations("7") == ["S"]
    assert keypad_combinations("11") == ["AA", "B"]
    assert keypad_combinations("111") == ["AAA", "AB", "BA", "C"]
    assert keypad_combinations("00") == ["ZZ"]
    assert keypad_combinations("772") == ["SSD", "TD"]
    assert keypad_combinations("1111") == ["AAAA", "AAB", "ABA", "AC", "BAA", "BB", "CA"]
    assert keypad_combinations("121") == ["ADA"]
    for s in ["", "1", "1111", "77777", "112233", "9999000"]:
        assert count_combinations(s) == len(keypad_combinations(s))
    assert count_combinations("1" * 40) > 10**9
    print("ok")

Complexity

Let n = len(digits), m = the most letters on one key (3 here), and R =
the number of answers.

• keypad_combinations: time O(R * n). Each answer costs O(n) to
  join, and every recursive branch leads to an answer. Sorting adds
  O(R log R * n) for comparisons; skip it if order does not matter.
  Space is O(n) for the recursion and path, plus O(R * n) for the output.
  R grows like the tribonacci numbers for a long run on a 3-letter key, so it
  is exponential in the worst case.
• count_combinations: time O(n * m), space O(n).

Test cases

• "" returns [] (no presses spell nothing; state your choice).
• "7" returns ["S"].
• "11" returns ["AA", "B"].
• "111" returns ["AAA", "AB", "BA", "C"].
• "1111" returns 7 strings: AAAA, AAB, ABA, AC, BAA, BB, CA. Note no group
  of 4, because key 1 has only 3 letters.
• "00" returns ["ZZ"]. A one-letter key never groups.
• "772" returns ["SSD", "TD"].
• "121" returns ["ADA"]. Different digits split the runs.
• "12a" raises ValueError.
• Count check: count_combinations("1" * 40) is above 10^9, so listing is not
  feasible there and only the DP answers it.

Follow-ups

1. Only count the results. Use the ways DP above. If the count can be
   huge, return it modulo 10^9 + 7. Run lengths can also be handled run by
   run: the answer is the product of f_m(run), where f_m counts
   compositions of run with parts at most m.
2. Wrap-around presses. On real phones, pressing past the last letter
   cycles back to the first. Then group size k maps to letter
   (k - 1) % len(letters), and groups have no size limit. Now two different
   cuts can spell the same string (on key 7, "7777" cut as 1+3 or 3+1
   both spell SS), so the output needs a set, and the count DP no
   longer counts distinct strings. Ask whether the interviewer wants distinct
   strings or distinct cuts.
3. A pause character. Add a separator such as _ that forces a cut
   ("1_1" means AA only). Split the input on the separator first and
   multiply the results of each piece; the core code does not change.
4. Only real words. Given a dictionary, return only spellings that are
   words. Build a trie of the words and walk it together with the
   backtracking; prune a branch as soon as the prefix is not in the trie.
   This turns an exponential search into one bounded by the dictionary.
5. Stream the results / k-th result. Turn backtrack into a generator so
   the caller can stop early. For the k-th string in sorted order, use the
   count DP to skip whole subtrees, the same way you find the k-th
   permutation.

Interviewer expectations

Mid-level (L4)

• Asks how runs work (what happens past the last letter, whether 0 and 1
  have letters) before coding.
• Writes working backtracking with a correct group-size limit.
• Walks through "111" by hand and gets the four answers.

Senior (L5)

• Notices that runs are independent and that no duplicates can occur, and
  explains why.
• States the exponential output size and gives the count DP without being
  pushed.
• Handles invalid input and the empty string on purpose, and tests the
  boundary where a run is longer than the key.

Staff (L6+)

• Sees that wrap-around breaks the no-duplicates argument and the count DP,
  and asks which answer the product needs.
• Proposes trie pruning for the dictionary version and generators or k-th
  indexing for large outputs.
• Keeps the keypad as a parameter so other layouts (or the classic 2–9
  layout) need no code change.