MediumHash TableStringUpdated Sep 2026

1138. Alphabet Board Path

Asked at Atlassian

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Hash Table

Companies

1

Problem

We have a board of lowercase letters laid out in rows of 6, like a keyboard:

abcde
fghij
klmno
pqrst
uvwxy
z

We start with our finger on a at row 0, column 0. For each character of a given string target, we must move the finger to that character's cell and then press it. Moving one cell up, down, left or right costs one move (U, D, L, R), and pressing the current letter costs one move (!). The finger may never leave the board — and note the last row holds only z, so the cells to the right of z do not exist.

Return any string of moves that types target in the minimum number of moves. Because the board is a grid, the shortest way to reach a letter is a fixed number of horizontal moves plus a fixed number of vertical moves; only the order of those moves is free, and the order matters because of the missing cells in the last row.

The board and one target

boardabcdefghijklmnopqrstuvwxyztarget = "leet" — start at a, then visit l, e, e, t inthat order
The finger starts on a and must visit each letter of the target in order, pressing ! at each one.

Constraints

  • ●1 <= target.length <= 100
  • ●target consists only of English lowercase letters

Examples

Example 1
Inputtarget = "leet"
OutputDDR!UURRR!!DDD!
WhyFrom a(0,0) go right twice and down once to reach l(2,1), press it. Then up twice and right three times to reach e(0,4), press it. e is already under the finger, so just press again. Finally down three times to t(3,4) and press.
Example 2
Inputtarget = "code"
OutputRR!DDRR!UUL!R!
WhyFrom a(0,0) go right twice to c(0,2), press. Down twice and right twice to o(3,4), press. Up twice and left once to d(0,3), press. Right once to e(0,4), press. Every step stays on the board.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Brute force: for each character, BFS to find the shortest path from current position to that character. That's O(26 * n) where n is the string length. Works but overly complex.

2

Key insight: compute the Manhattan distance for each character from 'a'. Move right/left for column differences, down/up for row differences. The tricky part is move ordering to stay on the board.

3

The board layout: row = (ch - 'a') / 6, col = (ch - 'a') % 6. But 'z' is at position (5, 0) and the grid is not perfectly rectangular - the last row has only one element. You must avoid moving through the gap.

4

Safe move ordering: if moving left or up, do those moves first (to avoid going off the board through the gap at the bottom-right). If moving right or down, do those moves last. This ensures you stay within bounds.

5

Edge cases: single character string, consecutive same characters (just press !), starting at 'z' and going to 'a'.

Optimal Approach

Step 1: Map each character to its (row, col) position on the board.
Step 2: Start at position (0, 0) for 'a'.
Step 3: For each target character:

  • Compute the row difference and col difference from current position.
  • If moving left (col decreases) or up (row decreases), issue those moves first.
  • If moving right (col increases) or down (row increases), issue those moves after.
  • End with '!' to press the character.
  • Update current position.

Walkthrough for target = "abc":

  • Start (0,0). To 'a'=(0,0): no moves. Path: !
  • To 'b'=(0,1): right 1. Path: R!
  • To 'c'=(0,2): right 1. Path: R!
  • Full: !R!R!

For target = "z":

  • Start (0,0). To 'z'=(5,0): down 5. Path: DDDDD!

Time: O(n) where n is the target length. Space: O(1) excluding output.

Move left/up first, then right/down

step 1: a -> labcdefghijklmnopqrstuvwxyzFrom a(0,0) to l(2,1): down 2, right 1 — no left or upmoves neededstep 2: l -> eabcdefghijklmnopqrstuvwxyzFrom l(2,1) to e(0,4): up 2 first, then right 3 — upfirst avoids nothing here, but it is the safe rulerow = (ch - 'a') // 6col = (ch - 'a') % 6order: L, U, R, D, then !
Doing the left and up moves before the right and down moves keeps the finger on real cells, which matters when z is involved.
ComplexityTime O(n)Space O(1)We do one constant-time position lookup and a fixed number of moves per character, so the work grows linearly with the target length; the output string itself is not counted.

What Trips People Up in Real Interviews

1

Ignoring the board boundary. You cannot move off the grid. The board is not a full rectangle - position (5,1) through (5,5) do not exist. Moving right from 'z' goes off the board.

2

Using Manhattan distance without considering move order. Moving right before up from 'z' could go through invalid positions. Left and up must come before right and down.

3

Trying to compute shortest path with BFS for each character. While BFS works, the direct Manhattan distance approach with proper move ordering is simpler and equally correct.

4

Forgetting to update the current position after reaching each character. The starting position for the next character is the position of the previous character, not (0,0).

5

Not handling consecutive identical characters. If the current and target characters are the same, just output '!' without any movement.

Solution Code

O(n) time
def alphabetBoardPath(target):
    def pos(ch):
        idx = ord(ch) - ord('a')
        return idx // 6, idx % 6

    result = []
    cr, cc = 0, 0
    for ch in target:
        tr, tc = pos(ch)
        dr, dc = tr - cr, tc - cc
        if dc < 0:
            result.append('L' * (-dc))
        if dr < 0:
            result.append('U' * (-dr))
        if dc > 0:
            result.append('R' * dc)
        if dr > 0:
            result.append('D' * dr)
        result.append('!')
        cr, cc = tr, tc
    return ''.join(result)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Alphabet Board Path problem?

Given a string target, build the path to type it on an alphabet board starting at 'a'. The board is a grid where you can move up, down, left, right, and press '!'. You must never go off the board. This problem tests your ability to plan moves while respecting grid boundaries.

How do you solve Alphabet Board Path?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Alphabet Board Path?

Alphabet Board Path is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Alphabet Board Path?
  • Ignoring the board boundary. You cannot move off the grid. The board is not a full rectangle - position (5,1) through (5,5) do not exist. Moving right from 'z' goes off the board.
  • Using Manhattan distance without considering move order. Moving right before up from 'z' could go through invalid positions. Left and up must come before right and down.
  • Trying to compute shortest path with BFS for each character. While BFS works, the direct Manhattan distance approach with proper move ordering is simpler and equally correct.
  • Forgetting to update the current position after reaching each character. The starting position for the next character is the position of the previous character, not (0,0).
  • Not handling consecutive identical characters. If the current and target characters are the same, just output '!' without any movement.