Type a word on a grid keyboard with a jump limit

The finger starts on any key that holds the first letter. Each next letter must sit within Manhattan distance k of where the finger is now. A letter can appear on several keys, so the real question is: after typing the first i letters, which keys could the finger be on? Call that set the frontier.

Greedy is wrong. Picking the nearest copy of each letter can strand you. Say a has copies at both ends of the board. The nearer one is fine for the next letter but cannot reach the letter after that. You have to carry every possible position forward, not just one.

Brute force. Try every choice of key for every letter (DFS). With c copies per letter this is O(c^L) for a word of length L. It is correct but explodes on a 1000-letter word with repeated keys.

Frontier DP (pairwise). The frontier for letter i+1 is every copy of word[i+1] that is within k of some key in the frontier for letter i. Only the set matters, not how you got there, so the state never grows past the number of copies of one letter. One step costs |frontier| * |copies of next letter|. If every letter is unique on the board this is O(L), which is the common case.

Frontier DP (grid BFS), for boards with many repeats. When both sets are large, the pairwise product can reach (m*n)^2 per step. On a grid with no blocked cells, the BFS distance between two cells equals their Manhattan distance. So run a multi-source BFS from the whole frontier, stopping at depth k. Every cell it reaches is within k of some frontier key. The new frontier is the copies of the next letter among the reached cells. That is O(m*n) per step no matter how many copies there are. The code picks whichever of the two costs is smaller at each step.

Small wins worth saying out loud.

• If any letter of the word is not on the board, answer False right away.
• A repeated letter ("ll") is still a full step. Staying put (distance 0) is always allowed, but the finger may also hop to another copy of the same letter, and that can matter later. Skipping the step is a classic bug.
• If k >= (m - 1) + (n - 1), every key reaches every other key, so the answer is just "all letters exist".
• If the frontier ever becomes empty, stop: no later letter can fix it.

Invariant. After processing word[0..i], frontier is exactly the set of keys holding word[i] that end some valid typing of word[0..i]. The word is typeable iff the frontier is non-empty after the last letter.

from collections import deque


def can_type(keyboard: list[str], k: int, word: str) -> bool:
    """Return True if `word` can be typed on `keyboard` with every move between
    consecutive letters at Manhattan distance <= k. The finger may start on any
    key that holds word[0]. Letters may appear on more than one key."""
    if k < 0:
        raise ValueError("k must be non-negative")
    if not word:
        return True
    m = len(keyboard)
    n = len(keyboard[0]) if m else 0

    positions: dict[str, list[tuple[int, int]]] = {}
    for r, row in enumerate(keyboard):
        for c, ch in enumerate(row):
            positions.setdefault(ch, []).append((r, c))

    if any(ch not in positions for ch in set(word)):
        return False
    if k >= (m - 1) + (n - 1):
        return True  # every key reaches every other key

    frontier: set[tuple[int, int]] = set(positions[word[0]])
    for ch in word[1:]:
        targets = positions[ch]
        if len(frontier) * len(targets) <= m * n:
            frontier = {
                (r2, c2)
                for (r2, c2) in targets
                if any(abs(r1 - r2) + abs(c1 - c2) <= k for (r1, c1) in frontier)
            }
        else:
            reached = _within_k(frontier, k, m, n)
            frontier = {p for p in targets if p in reached}
        if not frontier:
            return False
    return True


def _within_k(
    sources: set[tuple[int, int]], k: int, m: int, n: int
) -> set[tuple[int, int]]:
    """Cells within Manhattan distance k of any source. On an open grid the BFS
    distance equals the Manhattan distance, so a depth-limited BFS is exact."""
    seen = set(sources)
    queue = deque((p, 0) for p in sources)
    while queue:
        (r, c), d = queue.popleft()
        if d == k:
            continue
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append(((nr, nc), d + 1))
    return seen


if __name__ == "__main__":
    board = ["qwertyuiop", "asdfghjkl;", "zxcvbnm,./"]
    assert can_type(board, 2, "were")
    assert not can_type(board, 8, "quiz")  # i -> z is 9 apart
    assert can_type(board, 9, "quiz")
    assert not can_type(board, 9, "hello!")  # '!' is not on the board
    assert can_type(board, 0, "eee")  # stay on the key
    assert not can_type(board, 0, "er")
    assert can_type(board, 3, "")
    # Greedy trap: the nearer 'a' cannot reach 'c'; the far one can.
    trap = ["ba...a", ".....c"]
    assert can_type(trap, 1, "bac") is False
    assert can_type(trap, 1, "ac")
    assert can_type(["xa", "ax"], 1, "aaxa")
    assert can_type(["aaa", "cbb", "cab"], 1, "baccbb")  # hop c -> c
    print("ok")

Let the board be m x n, the word length L, and c_i the number of keys holding word[i].

• Building positions: O(m*n) time and space.
• Each letter step: O(min(c_i * c_{i+1}, m*n)) time. The pairwise branch runs when the product is at most m*n; otherwise the BFS branch costs O(m*n).
• Total: O(m*n + L * min(c^2, m*n)). With unique letters (a real keyboard) it is O(m*n + L). In the worst case it is O(L * m*n).
• Space: O(m*n) for positions and the BFS seen set; the frontier never holds more than the copies of one letter.

• ["qwertyuiop", "asdfghjkl;", "zxcvbnm,./"], k = 2, "were" → True (w-e 1, e-r 1, r-e 1).
• Same board, k = 8, "quiz" → False (q-u is 6 and u-i is 1, but i at (0,7) to z at (2,0) is 9).
• Same board, k = 9, "quiz" → True.
• Same board, any k, "hello!" → False (! is not a key).
• k = 0, "eee" → True (repeated letters stay put); k = 0, "er" → False.
• Empty word → True.
• Greedy trap: ["ba...a", ".....c"], k = 1, "bac" → False (the a next to b is 5 away from c; the a above c is 5 away from b). "ac" alone → True.
• Repeated keys: ["xa", "ax"], k = 1, "aaxa" → True.
• Double letter that must hop: ["aaa", "cbb", "cab"], k = 1, "baccbb" → True (b(1,1) → a(2,1) → c(2,0) → c(1,0) → b(1,1) → b(1,1); the second c must hop to the other copy, because only c(1,0) touches a b). Skipping repeated letters wrongly returns False.
• Single-cell board ["z"], "zzz" → True; "zy" → False.
• k at least (m-1)+(n-1): answer is True whenever every letter exists.

• Smallest k that works. Feasibility is monotone in k (a larger jump never hurts), so binary search k over [0, m+n-2] with can_type as the check: O(log(m+n)) extra factor. A direct alternative is a minimax DP: best[p] = the smallest maximum jump that ends at key p, updated with max(best[q], dist(q, p)) over copies of the previous letter.
• Shortest total travel. Replace the set with a dict cost[p] = least total distance to type the prefix ending on key p, minimizing over copies of the previous letter (still subject to <= k). Same loop shape, O(L * c^2). Two fingers turns this into the LeetCode 1320 style DP with a state of both finger positions.
• Return the actual key sequence. Store a parent pointer for each key in each frontier, then walk back from any key in the last frontier. Memory becomes O(L * c).
• Dead keys or blocked cells. Manhattan distance is no longer the travel distance. The BFS branch still works (it already walks the grid), so drop the pairwise branch, or precompute all-pairs BFS distances between letters if many words are queried.
• Many words against one board. Precompute, for every ordered pair of letters (a, b), which copies of b each copy of a can reach. With unique letters this is a 26 x 26 boolean table and each word check becomes O(L).

Mid-level (L4)

• Builds the letter-to-positions map and handles a missing letter.
• Gets a correct answer for unique keys, then notices that repeated keys need more than one position.
• Writes a working DFS or frontier solution with clear complexity.

Senior (L5)

• Explains why greedy (nearest copy) fails, with a small counterexample.
• Uses the frontier-set DP and argues why only the set of end keys matters.
• Covers the edge cases: k = 0, double letters (which may hop to another copy), empty word, large k short-circuit.
• Handles the minimum-k or minimum-travel follow-up by changing the DP value, not the structure.

Staff (L6+)

• Sees that the pairwise step can be (m*n)^2 and replaces it with a depth-limited multi-source BFS, choosing the cheaper method per step.
• Notes the BFS is exact only on an open grid and adapts it for blocked keys.
• Discusses precomputation for many queries and the memory tradeoff of path reconstruction.