# Minimum Distance to Type a Word Using Two Fingers
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers)
Canonical: https://scaleengineer.com/dsa/problems/minimum-distance-to-type-a-word-using-two-fingers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
![](https://assets.glich.co/dsa/minimum-distance-to-type-a-word-using-two-fingers/image0.png) 

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
## Top-Down Dynamic Programming (Memoization)
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.
**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.
**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)`.
### Explanation
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)`.

```java
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]);
    }
}
```
### 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.

## Bottom-Up Dynamic Programming with State Reduction
This approach uses bottom-up dynamic programming. It improves upon the naive recursive solution by recognizing a key property: when typing the `i`-th character, one of the fingers must have been on the `(i-1)`-th character. This insight allows us to reduce the state representation from three dimensions `(index, pos1, pos2)` to two dimensions `(index, other_finger_pos)`, leading to better time and space complexity.
**Time:** O(N * C). The outer loop runs N times, and the inner loop runs C times. · **Space:** O(N * C), where N is the word length and C is 27. This is for the 2D DP table.
**Pros:** More efficient in time and space than the 3D state approach.; Systematic bottom-up calculation can be more intuitive for some than recursion.
**Cons:** The space complexity is proportional to the length of the word, which can be improved.
### Explanation
We define `dp[i][j]` as the minimum cost to type the prefix `word[0...i]`, with one finger positioned at `word[i]` and the other finger at character `j`. The state is defined by `i`, the index of the character just typed, and `j`, the position of the other finger. `j` can be any of the 26 letters or the "free" state (represented by 26).

The DP table size will be `word.length() x 27`.

- **Initialization:** For the first character `word[0]`, we place one finger on it (cost 0) and the other finger is free. So, `dp[0][26] = 0`. All other `dp[0][j]` are initialized to infinity.
- **Transition:** To compute `dp[i][...]` from `dp[i-1][...]`, we consider typing `word[i]`. The previous character typed was `word[i-1]`. For every possible previous state `(i-1, k)` (where one finger is at `word[i-1]` and the other at `k`), we have two choices to type `word[i]`:
    1.  Move the finger from `word[i-1]` to `word[i]`. The other finger stays at `k`. The new state is `(i, k)`. The cost is `dp[i-1][k] + distance(word[i-1], word[i])`.
    2.  Move the finger from `k` to `word[i]`. The finger at `word[i-1]` now becomes the "other" finger. The new state is `(i, word[i-1])`. The cost is `dp[i-1][k] + distance(k, word[i])`.
- We update `dp[i][j]` by taking the minimum over all possibilities.
- **Final Answer:** After filling the table up to `i = word.length() - 1`, the minimum cost is the minimum value in the last row `dp[word.length() - 1]`.

```java
class Solution {
    public int minimumDistance(String word) {
        int n = word.length();
        // dp[i][j]: min cost to type word[0...i], with one finger at word[i]
        // and the other at character j. j=26 means the other finger is free.
        int[][] dp = new int[n][27];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE / 2);
        }

        dp[0][26] = 0;

        for (int i = 1; i < n; i++) {
            int prevChar = word.charAt(i - 1) - 'A';
            int currChar = word.charAt(i) - 'A';

            for (int k = 0; k < 27; k++) {
                if (dp[i - 1][k] == Integer.MAX_VALUE / 2) {
                    continue;
                }
                // Case 1: Move the finger from prevChar to currChar.
                int cost1 = dp[i - 1][k] + dist(prevChar, currChar);
                dp[i][k] = Math.min(dp[i][k], cost1);

                // Case 2: Move the finger from k to currChar.
                int cost2 = dp[i - 1][k] + dist(k, currChar);
                dp[i][prevChar] = Math.min(dp[i][prevChar], cost2);
            }
        }

        int minDistance = Integer.MAX_VALUE;
        for (int cost : dp[n - 1]) {
            minDistance = Math.min(minDistance, cost);
        }

        return minDistance;
    }
    
    private int[] getPos(int charIndex) {
        return new int[]{charIndex / 6, charIndex % 6};
    }

    private int dist(int charIndex1, int charIndex2) {
        if (charIndex1 == 26 || charIndex2 == 26) {
            return 0;
        }
        int[] pos1 = getPos(charIndex1);
        int[] pos2 = getPos(charIndex2);
        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    }
}
```
### Algorithm
1. Define a 2D DP table `dp[i][j]`, where `dp[i][j]` stores the minimum cost to type the prefix `word[0...i]`, with one finger at `word[i]` and the other at character `j`.
2. Initialize the DP table `dp[word.length()][27]` with a large value (infinity).
3. **Base Case:** For the first character `word[0]`, the cost is 0. One finger is placed on `word[0]` and the other is free. So, `dp[0][26] = 0` (where 26 represents the free state).
4. **Transition:** Iterate `i` from 1 to `word.length() - 1`. For each `i`, iterate through all possible previous 'other finger' positions `k` (from 0 to 26).
   - If `dp[i-1][k]` is finite, consider two ways to type `word[i]`:
     a. **Move the finger from `word[i-1]`:** The other finger stays at `k`. The cost is `dp[i-1][k] + dist(word[i-1], word[i])`. Update `dp[i][k]` with this new cost if it's smaller.
     b. **Move the finger from `k`:** The finger at `word[i-1]` now becomes the 'other' finger. The cost is `dp[i-1][k] + dist(k, word[i])`. Update `dp[i][word[i-1]]` with this new cost if it's smaller.
5. **Result:** After filling the table, the minimum total distance is the minimum value in the last row, `min(dp[word.length() - 1])`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient solution, achieved by optimizing the space complexity of the bottom-up DP approach. We observe that the calculation of the DP state for the current character `i` only depends on the DP states from the previous character `i-1`. This allows us to discard older states and use only two arrays (one for the previous state, one for the current state), reducing the space complexity from O(N*C) to O(C).
**Time:** O(N * C). The time complexity remains the same as the 2D DP approach. · **Space:** O(C), where C is 27. We only need space for two arrays of size C, which is constant space.
**Pros:** Optimal space complexity, using only constant extra space.; Maintains the optimal time complexity of the 2D DP approach.
**Cons:** The logic of swapping DP arrays can be slightly more complex to implement correctly compared to the 2D version.
### Explanation
Instead of a 2D DP table, we use a 1D array, `dp`, of size 27. `dp[j]` will represent the minimum cost to type the prefix up to the current character, with one finger on the current character and the other on `j`.

- **Initialization:** Before the main loop, we initialize a `dp` array representing the state after typing the first character. The cost is 0, one finger is on `word[0]`, and the other is free. We can set `dp[26] = 0` and all other `dp[j]` to infinity.
- **Transition:** We loop `i` from 1 to `word.length() - 1`. In each iteration, we compute the costs for the current character `word[i]` based on the costs from the previous character `word[i-1]`. We use a temporary `new_dp` array for this.
    - Let `prev_char = word.charAt(i-1)` and `curr_char = word.charAt(i)`.
    - We iterate through all possible positions `k` of the 'other' finger from the previous step. If `dp[k]` is a valid cost:
        1.  Calculate the cost of moving the finger from `prev_char` to `curr_char`. The other finger stays at `k`. Update `new_dp[k]`.
        2.  Calculate the cost of moving the finger from `k` to `curr_char`. The other finger is now at `prev_char`. Update `new_dp[prev_char]`.
    - After iterating through all `k`, `new_dp` contains the costs for step `i`. We then update `dp = new_dp` for the next iteration.
- **Final Answer:** After the loop finishes, the minimum value in the final `dp` array is the result.

```java
class Solution {
    public int minimumDistance(String word) {
        int n = word.length();
        // dp[j]: min cost to type prefix, with one finger at the last char
        // and the other at character j. j=26 means the other finger is free.
        int[] dp = new int[27];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);

        // Base case: After typing word[0], cost is 0, one finger is on word[0],
        // the other is free (represented by index 26).
        // We start the loop from i=1, so dp array represents state after word[i-1].
        // Initially, this means state after word[0]. But we can think of a virtual
        // state before word[0] where cost is 0 and one finger is free.
        dp[26] = 0;

        for (int i = 1; i < n + 1; i++) {
            int[] newDp = new int[27];
            Arrays.fill(newDp, Integer.MAX_VALUE / 2);
            int currChar = word.charAt(i - 1) - 'A';

            for (int k = 0; k < 27; k++) {
                if (dp[k] == Integer.MAX_VALUE / 2) {
                    continue;
                }
                // Case 1: Move the finger from k to currChar.
                // The other finger is now at prevChar (which is k).
                // This logic is slightly different from the 2D version. Let's re-align.
                // Let dp[k] be min cost to type word[0...i-2], one finger at word[i-2], other at k.
                // To type word[i-1]:
                int prevChar = (i > 1) ? word.charAt(i - 2) - 'A' : 26;
                
                // Move finger from prevChar to currChar. Other finger stays at k.
                int cost1 = dp[k] + dist(prevChar, currChar);
                newDp[k] = Math.min(newDp[k], cost1);

                // Move finger from k to currChar. Other finger becomes prevChar.
                int cost2 = dp[k] + dist(k, currChar);
                newDp[prevChar] = Math.min(newDp[prevChar], cost2);
            }
            dp = newDp;
        }

        int minDistance = Integer.MAX_VALUE;
        for (int cost : dp) {
            minDistance = Math.min(minDistance, cost);
        }

        return minDistance;
    }
    
    // The code below is a cleaner implementation of the same logic.
    public int minimumDistance(String word) {
        int[] dp = new int[27]; // dp[j] = min_cost with one finger at last char, other at j
        
        for (int i = 0; i < word.length() - 1; i++) {
            int from = word.charAt(i) - 'A';
            int to = word.charAt(i + 1) - 'A';
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < 27; j++) {
                // Cost to move the other finger (at j) to 'to'
                min = Math.min(min, dp[j] + dist(j, to));
            }
            for (int j = 0; j < 27; j++) {
                // Cost to move the finger from 'from' to 'to'
                dp[j] += dist(from, to);
            }
            // Update the state where the other finger moved
            dp[from] = Math.min(dp[from], min);
        }
        
        return dp[word.charAt(word.length() - 1) - 'A'];
    }

    private int[] getPos(int charIndex) {
        return new int[]{charIndex / 6, charIndex % 6};
    }

    private int dist(int charIndex1, int charIndex2) {
        if (charIndex1 == 26 || charIndex2 == 26) {
            return 0;
        }
        int[] pos1 = getPos(charIndex1);
        int[] pos2 = getPos(charIndex2);
        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    }
}
```
### Algorithm
1. Instead of a 2D DP table, use a 1D array `dp` of size 27. `dp[j]` will store the minimum cost to type the prefix ending at the *previous* character, with one finger there and the other at `j`.
2. **Initialization:** Initialize `dp` for the state before typing the first character. Since there's no cost yet and both fingers are free, we can model this by considering the cost to type the first character. Initialize `dp` with a large value, and set `dp[26] = 0` (representing a cost of 0 with one finger free, ready to move to the first character).
3. **Transition:** Loop `i` from 1 to `word.length() - 1`.
   - Inside the loop, create a `new_dp` array of size 27, initialized to infinity.
   - For each previous 'other finger' position `k` (from 0 to 26):
     - If `dp[k]` is finite, calculate the two possible moves to type `word[i]`:
       a. **Move finger from `word[i-1]`:** Cost is `dp[k] + dist(word[i-1], word[i])`. Update `new_dp[k]`.
       b. **Move finger from `k`:** Cost is `dp[k] + dist(k, word[i])`. Update `new_dp[word[i-1]]`.
   - After the inner loop, `new_dp` holds the costs for the current step `i`. Assign `dp = new_dp`.
4. **Result:** After the main loop finishes, the minimum value in the final `dp` array is the answer.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumDistance(string word) {
    int n = word.size();
    const int inf = 1 << 30;
    vector<vector<vector<int>>> f(
        n, vector<vector<int>>(26, vector<int>(26, inf)));
    for (int j = 0; j < 26; ++j) {
      f[0][word[0] - 'A'][j] = 0;
      f[0][j][word[0] - 'A'] = 0;
    }
    for (int i = 1; i < n; ++i) {
      int a = word[i - 1] - 'A';
      int b = word[i] - 'A';
      int d = dist(a, b);
      for (int j = 0; j < 26; ++j) {
        f[i][b][j] = min(f[i][b][j], f[i - 1][a][j] + d);
        f[i][j][b] = 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] = min(f[i][b][j], f[i - 1][k][a] + t);
            f[i][j][b] = min(f[i][j][b], f[i - 1][a][k] + t);
          }
        }
      }
    }
    int ans = inf;
    for (int j = 0; j < 26; ++j) {
      ans = min(ans, f[n - 1][word[n - 1] - 'A'][j]);
      ans = min(ans, f[n - 1][j][word[n - 1] - 'A']);
    }
    return ans;
  }
  int dist(int a, int b) {
    int x1 = a / 6, y1 = a % 6;
    int x2 = b / 6, y2 = b % 6;
    return abs(x1 - x2) + abs(y1 - y2);
  }
};

```

### Python

```python
class Solution:
    def minimumDistance(self, word: str) -> int: def dist(a: int, b: int) -> int: x1, y1 = divmod(a, 6) x2, y2 = divmod(b, 6) return abs(x1 - x2) + abs(y1 - y2) n = len(word) f = [[[inf] * 26 for _ in range(26)] for _ in range(n)] for j in range(26): f[0][ord(word[0]) - ord('A')][j] = 0 f[0][j][ord(word[0]) - ord('A')] = 0 for i in range(1, n): a, b = ord(word[i - 1]) - ord('A'), ord(word[i]) - ord('A') d = dist(a, b) for j in range(26): f[i][b][j] = min(f[i][b][j], f[i - 1][a][j] + d) f[i][j][b] = min(f[i][j][b], f[i - 1][j][a] + d) if j == a: for k in range(26): t = dist(k, b) f[i][b][j] = min(f[i][b][j], f[i - 1][k][a] + t) f[i][j][b] = min(f[i][j][b], f[i - 1][a][k] + t) a = min(f[n - 1][ord(word[- 1]) - ord('A')]) b = min(f[n - 1][j][ord(word[- 1]) - ord('A')] for j in range(26)) return int(min(a, b))

```