Alphabet Board Path
Asked at Atlassian
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
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.
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.
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.
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.
Visual walkthrough for target = "zig":
Board positions: a=(0,0), z=(5,0), i=(1,2), g=(1,1).
Start at a=(0,0).
To z=(5,0): col same, row diff=5. Move down 5 times. Press !. Path: DDDDD!
Position now at z=(5,0).
To i=(1,2): row diff=-4 (up 4), col diff=2 (right 2).
Move up first (left/up before right/down): UUUU. Then right: RR. Press !. Path: UUUURR!
Position now at i=(1,2).
To g=(1,1): row same, col diff=-1 (left 1).
Move left: L. Press !. Path: L!
Full path: DDDDD!UUUURR!L!
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.
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.