LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers

The keyboard is arranged in a fixed grid layout containing the 26 uppercase English letters. Each letter has a coordinat

leetcodehardstringdynamic-programming

LeetCode Problem 1320

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The keyboard is arranged in a fixed grid layout containing the 26 uppercase English letters. Each letter has a coordinate in the grid:

A B C D E F
G H I J K L
M N O P Q R
S T U V W X
Y Z

The coordinates are assigned row by row. For example:

  • A -> (0, 0)
  • B -> (0, 1)
  • C -> (0, 2)
  • P -> (2, 3)
  • Z -> (4, 1)

The distance between two letters is the Manhattan distance:

$d = |x_1 - x_2| + |y_1 - y_2|$

We are given a string word, and we must type it using exactly two fingers. At every step, we may choose either finger to press the next character. Moving a finger from one letter to another incurs the Manhattan distance cost. However, the initial placement of both fingers is free, meaning the first time a finger is used, it can start directly on the needed letter with cost 0.

The goal is to minimize the total movement distance required to type the entire word.

The input consists of a single uppercase string with length between 2 and 300. The relatively large input size immediately suggests that exponential exploration of all possibilities will not work. Since each character may potentially be typed by either finger, a naive solution would branch repeatedly and become infeasible.

A few important observations emerge from the constraints:

  • Only uppercase English letters appear, so there are only 26 possible keyboard positions.
  • The word length can reach 300, which is too large for brute-force recursion without memoization.
  • Because the alphabet size is small and fixed, dynamic programming over finger positions becomes practical.

Several edge cases are important:

  • Consecutive identical characters, where moving a finger may cost 0.
  • Very short words such as length 2, where one finger can type each character for free.
  • Words where one finger should remain stationary for many steps while the other does most of the movement.
  • Situations where greedily choosing the nearest finger locally leads to a globally suboptimal solution.

The main challenge is deciding which finger should type each upcoming character so that future movement costs remain minimal.

Approaches

Brute Force

A brute-force solution tries every possible assignment of characters to the two fingers.

For each character in the word, we have two choices:

  1. Type it with finger one.
  2. Type it with finger two.

After choosing, we update that finger's position and recursively continue to the next character.

Because every character introduces two branching possibilities, the total number of states grows exponentially. In the worst case, this becomes approximately:

$2^n$

where n is the length of the word.

Although this approach eventually finds the optimal answer because it explores all possibilities, it is far too slow for n = 300.

Key Insight

The important observation is that many recursive states repeat.

At any point during typing, the future cost depends only on:

  • The current index in the word.
  • The position of finger one.
  • The position of finger two.

The exact sequence of moves used to reach this configuration does not matter. This overlapping-subproblem structure makes dynamic programming appropriate.

Since there are only 26 possible finger positions and at most 300 indices, the number of distinct states is manageable.

We can define a DP state representing the minimum cost after processing part of the word while the two fingers occupy specific letters.

For each next character, we transition by moving either finger to the new letter and updating the minimum cost accordingly.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explores every possible finger assignment
Optimal Dynamic Programming O(n × 26 × 26) O(26 × 26) Reuses overlapping states efficiently

Algorithm Walkthrough

Step 1: Convert Letters Into Keyboard Coordinates

Each letter maps naturally into a grid coordinate.

For a letter index i from 0 to 25:

row = i // 6
col = i % 6

This allows us to compute Manhattan distances efficiently.

Step 2: Build a Distance Function

We create a helper function that returns the Manhattan distance between two letters.

If a finger has not been used yet, we represent its position with -1. Moving from an unused finger position costs 0, because initial placement is free.

Step 3: Define the DP State

We maintain a dictionary:

dp[(finger1, finger2)] = minimum cost

This means:

  • finger1 is the current position of the first finger.
  • finger2 is the current position of the second finger.
  • The value is the minimum total distance needed to reach this configuration after typing some prefix of the word.

Initially:

dp[(-1, -1)] = 0

Both fingers are unused.

Step 4: Process Characters One by One

For each character in the word:

  1. Convert it into its numeric index.
  2. Create a new DP table for the next states.
  3. For every existing state:
  • Move finger one to the new character.
  • Move finger two to the new character.
  1. Update the minimum costs accordingly.

This explores all valid assignments while avoiding recomputation.

Step 5: Keep Only the Best Cost Per State

Different paths may produce the same finger configuration.

We only keep the minimum cost for each state because any larger value is never useful in future transitions.

Step 6: Return the Minimum Final Cost

After processing all characters, the answer is the minimum value among all remaining DP states.

Why it works

The DP invariant is that after processing the first i characters, every stored state represents the minimum possible cost to reach those exact finger positions.

When processing the next character, the only valid actions are moving finger one or finger two to that character. Since all previous states are already optimal, and we examine both valid transitions, the resulting states also remain optimal.

Because every possible finger assignment is represented through transitions, the algorithm eventually considers all valid typing strategies while eliminating redundant recomputation.

Python Solution

class Solution:
    def minimumDistance(self, word: str) -> int:
        from collections import defaultdict
        from typing import Dict, Tuple

        def get_distance(a: int, b: int) -> int:
            if a == -1 or b == -1:
                return 0

            ax, ay = divmod(a, 6)
            bx, by = divmod(b, 6)

            return abs(ax - bx) + abs(ay - by)

        dp: Dict[Tuple[int, int], int] = {(-1, -1): 0}

        for ch in word:
            current = ord(ch) - ord('A')
            next_dp = defaultdict(lambda: float('inf'))

            for (finger1, finger2), cost in dp.items():
                move_first = cost + get_distance(finger1, current)

                if move_first < next_dp[(current, finger2)]:
                    next_dp[(current, finger2)] = move_first

                move_second = cost + get_distance(finger2, current)

                if move_second < next_dp[(finger1, current)]:
                    next_dp[(finger1, current)] = move_second

            dp = next_dp

        return min(dp.values())

The implementation begins by defining a helper function for Manhattan distance calculation. The special value -1 represents an unused finger, and transitions from -1 cost zero because initial placement is free.

The DP table stores the minimum cost for every pair of finger positions. We initialize with both fingers unused.

For every character in the word, we compute all possible next states. From each existing configuration, we try:

  • Moving the first finger to the new character.
  • Moving the second finger to the new character.

The new state is updated only if the newly computed cost is smaller than the previously stored value.

After processing all characters, the smallest value in the DP table represents the optimal answer.

Go Solution

func minimumDistance(word string) int {
	type State struct {
		f1 int
		f2 int
	}

	getDistance := func(a, b int) int {
		if a == -1 || b == -1 {
			return 0
		}

		ax, ay := a/6, a%6
		bx, by := b/6, b%6

		if ax < bx {
			ax, bx = bx, ax
		}

		if ay < by {
			ay, by = by, ay
		}

		return (ax - bx) + (ay - by)
	}

	dp := map[State]int{
		{-1, -1}: 0,
	}

	for _, ch := range word {
		current := int(ch - 'A')
		nextDP := make(map[State]int)

		for state, cost := range dp {
			firstCost := cost + getDistance(state.f1, current)
			firstState := State{current, state.f2}

			if old, exists := nextDP[firstState]; !exists || firstCost < old {
				nextDP[firstState] = firstCost
			}

			secondCost := cost + getDistance(state.f2, current)
			secondState := State{state.f1, current}

			if old, exists := nextDP[secondState]; !exists || secondCost < old {
				nextDP[secondState] = secondCost
			}
		}

		dp = nextDP
	}

	answer := int(^uint(0) >> 1)

	for _, cost := range dp {
		if cost < answer {
			answer = cost
		}
	}

	return answer
}

The Go implementation follows the same DP strategy as the Python version. Since Go does not support tuple keys directly, a small State struct is used as the map key.

The DP table is represented with a map[State]int. Before updating a state, we check whether the state already exists and whether the new cost is smaller.

Go integers are sufficient because the maximum possible total distance is very small compared to integer limits.

Worked Examples

Example 1

word = "CAKE"

Character Mapping

Character Index Coordinate
C 2 (0, 2)
A 0 (0, 0)
K 10 (1, 4)
E 4 (0, 4)

DP Transitions

Initial State

State Cost
(-1, -1) 0

After Typing 'C'

State Cost
(2, -1) 0
(-1, 2) 0

After Typing 'A'

From (2, -1):

  • Move finger one: distance 2
  • Move finger two: distance 0

From (-1, 2):

  • Move finger one: distance 0
  • Move finger two: distance 2

Resulting states:

State Cost
(0, -1) 2
(2, 0) 0
(0, 2) 0
(-1, 0) 2

After Typing 'K'

The best resulting configuration becomes:

State Cost
(10, 0) 0
(0, 10) 0

One finger remains on A, while the other types K for free.

After Typing 'E'

Moving from K to E costs 1.

Final answer:

3

Example 2

word = "HAPPY"

Character Coordinates

Character Coordinate
H (1, 1)
A (0, 0)
P (2, 3)
P (2, 3)
Y (4, 0)

A good strategy is:

  1. Finger one types H
  2. Finger one moves to A, cost 2
  3. Finger two starts on P, cost 0
  4. Finger two stays on P, cost 0
  5. Finger one moves from A to Y, cost 4

Total:

2 + 4 = 6

Complexity Analysis

Measure Complexity Explanation
Time O(n × 26 × 26) At each character, all finger position pairs may be explored
Space O(26 × 26) DP stores states for finger position combinations

The DP table contains at most 27 × 27 states because each finger may occupy one of 26 letters or the unused position -1.

For every character in the word, we iterate through all possible states and generate two transitions. Since the alphabet size is constant, the algorithm is effectively linear with respect to the word length.

Test Cases

solution = Solution()

assert solution.minimumDistance("CAKE") == 3  # provided example
assert solution.minimumDistance("HAPPY") == 6  # provided example

assert solution.minimumDistance("AA") == 0  # repeated same character
assert solution.minimumDistance("AB") == 0  # each finger can type one letter
assert solution.minimumDistance("ABA") == 0  # reuse both fingers efficiently

assert solution.minimumDistance("ABCDE") == 3  # sequential nearby letters
assert solution.minimumDistance("AZAZ") == 0  # alternate fingers perfectly
assert solution.minimumDistance("YEAR") == 7  # mixed movement pattern

assert solution.minimumDistance("QWERTY") >= 0  # general correctness
assert solution.minimumDistance("TYPEWRITER") >= 0  # longer word

long_word = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
assert solution.minimumDistance(long_word) >= 0  # stress test across alphabet

assert solution.minimumDistance("PPPPPP") == 0  # no movement required

Test Summary

Test Why
"CAKE" Validates official example
"HAPPY" Validates second official example
"AA" Tests repeated characters
"AB" Tests free initial placement
"ABA" Tests optimal reuse of fingers
"ABCDE" Tests sequential movement
"AZAZ" Tests alternating finger usage
"YEAR" Tests irregular movement
"QWERTY" General correctness
"TYPEWRITER" Longer realistic input
Alphabet string Stress test over many letters
"PPPPPP" Ensures zero repeated movement

Edge Cases

Repeated Consecutive Characters

A word like "AAAAAA" is an important edge case because the optimal movement cost should remain zero after the first press. A buggy implementation might accidentally add movement cost even when the finger remains on the same key. This solution handles the case correctly because the Manhattan distance from a letter to itself is zero.

Free Initial Finger Placement

The problem explicitly states that both fingers may start anywhere for free. This creates cases like "AB" where the optimal answer is zero because one finger starts on A and the other starts on B. Incorrect solutions sometimes force movement from the first typed character. This implementation avoids that issue by representing unused fingers with -1 and returning distance zero whenever a finger is used for the first time.

Choosing the Globally Optimal Finger

Greedy local decisions can fail badly. For example, assigning the currently closest finger to the next character may produce larger future movement costs. The DP solution avoids this pitfall by exploring both possibilities at every step and storing the minimum achievable cost for every finger configuration.

Maximum Length Input

The input length can reach 300, which makes exponential recursion infeasible. The DP approach remains efficient because the number of possible finger states is bounded by the fixed alphabet size. Even at maximum input size, the algorithm performs comfortably within limits.