Scale Engineer

Minimum Distance to Type a Word Using Two Fingers

Hard
#1229Time: O(N * C^2), where N is the length of the word and C is 27. Each state `(index, pos1, pos2)` is computed only once.Space: O(N * C^2), where N is the length of the word and C is the number of possible finger positions (27). This is for the memoization table and recursion stack.
Patterns
Dynamic Programming
Data structures
String

Prompt

You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.

  • For example, the letter 'A' is located at coordinate (0, 0), the letter 'B' is located at coordinate (0, 1), the letter 'P' is located at coordinate (2, 3) and the letter 'Z' is located at coordinate (4, 1).

Given the string word, return the minimum total distance to type such string using only two fingers.

The distance between coordinates (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Note that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

 

Example 1:

Input: word = "CAKE"
Output: 3
Explanation: Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Example 2:

Input: word = "HAPPY"
Output: 6
Explanation: Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

 

Constraints:

  • 2 <= word.length <= 300
  • word consists of uppercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion with memoization, which is a top-down dynamic programming technique. It's a direct translation of the problem's recursive structure. The state of our recursive function is defined by the current index in the word we need to type, and the current positions of the two fingers. While intuitive, this method is not the most efficient due to its large state space.

Algorithm

  1. Create a helper function getPos(char c) to get the (x, y) coordinates for each character on the 6-column keyboard layout.
  2. Create a helper function dist(char_idx1, char_idx2) to calculate the Manhattan distance. If one of the indices represents the initial "free" state (e.g., index 26), the distance is 0.
  3. Create a 3D array memo[word.length()][27][27] for memoization, initialized with a value indicating that the state has not been computed.
  4. Implement a recursive function solve(index, pos1, pos2):
    • Base Case: If index reaches the end of the word (word.length()), it means all characters have been typed. Return 0.
    • Memoization Check: If memo[index][pos1][pos2] has been computed, return the stored value.
    • Recursive Step: Get the target character target = word.charAt(index). We have two choices: a. Move finger 1 from pos1 to target. The cost is dist(pos1, target) + solve(index + 1, target, pos2). b. Move finger 2 from pos2 to target. The cost is dist(pos2, target) + solve(index + 1, pos1, target).
    • Store the minimum of the two costs in memo[index][pos1][pos2] and return it.
  5. The main function starts the process by calling solve(0, 26, 26), where 26 represents the initial free state for both fingers.

Walkthrough

We define a recursive function, say solve(index, finger1_pos, finger2_pos), which returns the minimum cost to type the rest of the word from index onwards, given the fingers are at finger1_pos and finger2_pos.

The positions can be represented by integers 0-25 for 'A'-'Z', and a special value (e.g., 26) for the initial "free" state where a move costs 0. The distance between a finger in the free state and any character is 0.

The base case for the recursion is when index reaches the end of the word. In this case, no more typing is needed, so the cost is 0.

In the recursive step for solve(index, finger1_pos, finger2_pos), we need to type word[index]. We have two choices:

  1. Use finger 1: The cost is distance(finger1_pos, word[index]) plus the cost of typing the rest of the word, which is solve(index + 1, word[index], finger2_pos).
  2. Use finger 2: The cost is distance(finger2_pos, word[index]) plus the cost of typing the rest of the word, which is solve(index + 1, finger1_pos, word[index]).

The function returns the minimum of these two choices. To avoid recomputing results for the same state, we use a 3D memoization table memo[index][finger1_pos][finger2_pos]. The initial call to the function will be solve(0, 26, 26).

class Solution {    private Integer[][][] memo;    private String word;     public int minimumDistance(String word) {        this.word = word;        // memo[index][finger1_pos][finger2_pos]        this.memo = new Integer[word.length()][27][27];        return solve(0, 26, 26);    }     private int solve(int index, int pos1, int pos2) {        if (index == word.length()) {            return 0;        }        if (memo[index][pos1][pos2] != null) {            return memo[index][pos1][pos2];        }         int targetCharIndex = word.charAt(index) - 'A';         // Option 1: Use finger 1 to type the target character        int cost1 = dist(pos1, targetCharIndex) + solve(index + 1, targetCharIndex, pos2);         // Option 2: Use finger 2 to type the target character        int cost2 = dist(pos2, targetCharIndex) + solve(index + 1, pos1, targetCharIndex);         return memo[index][pos1][pos2] = Math.min(cost1, cost2);    }        private int[] getPos(int charIndex) {        return new int[]{charIndex / 6, charIndex % 6};    }     private int dist(int charIndex1, int charIndex2) {        if (charIndex1 == 26) { // Free finger            return 0;        }        int[] pos1 = getPos(charIndex1);        int[] pos2 = getPos(charIndex2);        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);    }}

Complexity

Time

O(N * C^2), where N is the length of the word and C is 27. Each state `(index, pos1, pos2)` is computed only once.

Space

O(N * C^2), where N is the length of the word and C is the number of possible finger positions (27). This is for the memoization table and recursion stack.

Trade-offs

Pros

  • Conceptually straightforward and closely follows the problem's recursive definition.

Cons

  • High space complexity due to the 3D memoization table.

  • High time complexity because of the large state space (index, pos1, pos2).

Solutions

class Solution {public  int minimumDistance(String word) {    int n = word.length();    final int inf = 1 << 30;    int[][][] f = new int[n][26][26];    for (int[][] g : f) {      for (int[] h : g) {        Arrays.fill(h, inf);      }    }    for (int j = 0; j < 26; ++j) {      f[0][word.charAt(0) - 'A'][j] = 0;      f[0][j][word.charAt(0) - 'A'] = 0;    }    for (int i = 1; i < n; ++i) {      int a = word.charAt(i - 1) - 'A';      int b = word.charAt(i) - 'A';      int d = dist(a, b);      for (int j = 0; j < 26; ++j) {        f[i][b][j] = Math.min(f[i][b][j], f[i - 1][a][j] + d);        f[i][j][b] = Math.min(f[i][j][b], f[i - 1][j][a] + d);        if (j == a) {          for (int k = 0; k < 26; ++k) {            int t = dist(k, b);            f[i][b][j] = Math.min(f[i][b][j], f[i - 1][k][a] + t);            f[i][j][b] = Math.min(f[i][j][b], f[i - 1][a][k] + t);          }        }      }    }    int ans = inf;    for (int j = 0; j < 26; ++j) {      ans = Math.min(ans, f[n - 1][j][word.charAt(n - 1) - 'A']);      ans = Math.min(ans, f[n - 1][word.charAt(n - 1) - 'A'][j]);    }    return ans;  }private  int dist(int a, int b) {    int x1 = a / 6, y1 = a % 6;    int x2 = b / 6, y2 = b % 6;    return Math.abs(x1 - x2) + Math.abs(y1 - y2);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem