leetcode solution

Minimum Distance Using Two Fingers – DP Solution

by

Typing on a keyboard with two fingers might sound inefficient, but what if you could optimize finger movement to minimize effort?

That’s exactly what the problem “Minimum Distance to Type a Word Using Two Fingers” focuses on. It’s a classic dynamic programming + optimization problem often asked in coding interviews and platforms like LeetCode.

Let’s break it down in a simple and intuitive way.

🧠 Problem Understanding

You are given a string word consisting of uppercase English letters.

You have two fingers, and both can start anywhere on the keyboard.

The keyboard layout is like this:

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

👉 Each move costs the Manhattan distance between characters.

Goal:

Minimize the total distance required to type the word using two fingers.

✨ Key Insight

At each step:

  • You can either move finger 1 or finger 2 to type the next character.
  • Choose the option that results in minimum total movement.

This naturally leads to a Dynamic Programming (DP) problem.

🔁 Approach (Dynamic Programming)

We define a DP state:

dp[i][j] = minimum distance when:
- One finger is at letter i
- Other finger is at letter j

But we optimize further:

👉 Instead of tracking both fingers explicitly, we track:

  • Current position
  • “Free finger” movement advantage

📍 Distance Function

We convert each character into coordinates:

row = (ord(char) - ord('A')) // 6
col = (ord(char) - ord('A')) % 6

Distance formula:

distance = |x1 - x2| + |y1 - y2|

⚡ Optimized DP Solution

Python Code:

class Solution:
    def minimumDistance(self, word: str) -> int:
        def get_pos(c):
            idx = ord(c) - ord('A')
            return idx // 6, idx % 6

        def dist(a, b):
            if a is None or b is None:
                return 0
            x1, y1 = get_pos(a)
            x2, y2 = get_pos(b)
            return abs(x1 - x2) + abs(y1 - y2)

        dp = {None: 0}

        for i in range(len(word) - 1):
            curr = word[i]
            nxt = word[i + 1]
            new_dp = {}

            for free, val in dp.items():
                # Case 1: Use same finger
                new_dp[free] = max(
                    new_dp.get(free, float('-inf')),
                    val
                )

                # Case 2: Use free finger
                saving = dist(curr, nxt) - dist(free, nxt)
                new_dp[curr] = max(
                    new_dp.get(curr, float('-inf')),
                    val + saving
                )

            dp = new_dp

        total = 0
        for i in range(len(word) - 1):
            total += dist(word[i], word[i + 1])

        return total - max(dp.values())

🧩 Intuition Simplified

  • If you type with one finger only, you incur full cost.
  • The second finger helps you save distance.
  • DP tracks the maximum saving possible.
  • Final answer = total cost – maximum saving

⏱ Time & Space Complexity

  • Time Complexity: O(n * 26)
  • Space Complexity: O(26)

👉 Efficient enough even for large inputs.

🔍 Example

Input:

word = "CAKE"

Output:

3

Explanation:

Optimal finger usage reduces unnecessary movement.

🚀 Why This Problem Matters

  • Tests state optimization
  • Introduces 2-pointer DP thinking
  • Helps in solving similar problems involving:
    • Multiple agents
    • Movement cost minimization

💡 Pro Tip

This is a classic example where:

“Tracking savings is easier than tracking cost.”

🏁 Final Thoughts

The “Minimum Distance to Type a Word Using Two Fingers” problem is a brilliant mix of:

  • Geometry (grid distance)
  • Dynamic Programming
  • Optimization mindset

Once you understand the “saving approach”, the problem becomes much easier and even elegant.

Leave a Comment