Minimum Distance to Type a Word Using Two Fingers

Hard
1507.

Minimum Distance to Type a Word Using Two Fingers

Minimum Distance to Type a Word Using Two Fingers is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

A keyboard places the 26 capital letters on a grid six keys wide, in order: A–F on row 0, G–L on row 1, M–R on row 2, S–X on row 3 and Y, Z on row 4. In other words the i-th letter (0-based) sits at row i / 6, column i % 6. The distance between two keys at (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

You type the string word using two fingers. Each finger may start on any key for free — the first press of each finger costs nothing. After that, every press costs the distance the finger moves from the key it pressed last. Either finger may type any letter.

Return the minimum total distance needed to type word.

Example 1

Input
word = "KAIRO"
Output
6
Explanation
One finger types K then R (distance 2); the other types A, I, O (distances 3 and 1).

Example 2

Input
word = "CODEKAIRO"
Output
13

Example 3

Input
word = "AZ"
Output
0
Explanation
Each finger presses one key, and first presses are free.

Constraints

  • 2 <= word.length <= 300
  • word consists of uppercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var minimumDistance = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Distance to Type a Word Using Two Fingers — Solution

Minimum Distance to Type a Word Using Two Fingers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Distance to Type a Word Using Two Fingers is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A keyboard places the 26 capital letters on a grid six keys wide, in order: A–F on row 0, G–L on row 1, M–R on row 2, S–X on row 3 and Y, Z on row 4. In other words the i-th letter (0-based) sits at row i / 6, column i % 6. The distance between two keys at (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

You type the string word using two fingers. Each finger may start on any key for free — the first press of each finger costs nothing. After that, every press costs the distance the finger moves from the key it pressed last. Either finger may type any letter.

Return the minimum total distance needed to type word.

Example 1

Input: word = "KAIRO"
Output: 6
Explanation: One finger types K then R (distance 2); the other types A, I, O (distances 3 and 1).

Example 2

Input: word = "CODEKAIRO"
Output: 13

Example 3

Input: word = "AZ"
Output: 0
Explanation: Each finger presses one key, and first presses are free.

Constraints

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

Hints for Minimum Distance to Type a Word Using Two Fingers

  1. Hint 1

    After typing word[i], one finger is certainly resting on word[i]. What else do you need to know?

  2. Hint 2

    Only the position of the other finger matters — or the fact that it has not been used yet. That is 27 possible states.

  3. Hint 3

    Let dp[o] be the least cost so far with the other finger on key o (26 = unused). For the next letter, either the finger on word[i] moves (o unchanged) or the other finger moves from o (free if unused) and the old finger becomes the 'other' one, resting on word[i].

How to solve Minimum Distance to Type a Word Using Two Fingers

The state after typing a prefix is the pair of finger positions, but one of them is always the last letter typed — so the only free information is where the other finger is, or that it has never been used. That collapses the state to 27 values per position.

Approach

  1. Let dist(a, b) be the grid distance, with dist(26, b) = 0 for an unused finger.
  2. Start with dp[26] = 0 after the first letter (typed by one finger for free) and every other dp value infinite.
  3. For each next letter cur with previous letter prev, build next: for every finite dp[o], set next[o] = min(next[o], dp[o] + dist(prev, cur)) (the finger on prev types cur) and next[prev] = min(next[prev], dp[o] + dist(o, cur)) (the other finger types cur).
  4. After the last letter, return the minimum over dp.

Why it works

Every typing plan corresponds to a path through these states: at each letter exactly one of the two fingers presses it, and the finger that does not press keeps its position. Because the costs of later presses depend only on the two current positions, keeping the minimum cost per state loses nothing, and the two transitions enumerate both possible choices.

Complexity

  • Time — O(27 · n)
  • Space — O(27)

Pitfalls

  • The second finger's first press is free — model the unused state explicitly rather than starting it on some key.
  • When the other finger types, the finger that typed prev becomes the new 'other' finger at prev.
  • Letter i is at row i / 6 and column i % 6 — integer division, six keys per row.

Reference solution

Python

def minimumDistance(word: str) -> int:
    def dist(a, b):
        if a == 26:
            return 0
        return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

    INF = float('inf')
    dp = [INF] * 27
    dp[26] = 0
    for i in range(1, len(word)):
        prev = ord(word[i - 1]) - 65
        cur = ord(word[i]) - 65
        nxt = [INF] * 27
        for o in range(27):
            if dp[o] == INF:
                continue
            a = dp[o] + dist(prev, cur)
            if a < nxt[o]:
                nxt[o] = a
            b = dp[o] + dist(o, cur)
            if b < nxt[prev]:
                nxt[prev] = b
        dp = nxt
    return min(dp)

Java

static int keyDistance(int a, int b) {
    if (a == 26) return 0;
    return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);
}

public static int minimumDistance(String word) {
    final int INF = Integer.MAX_VALUE / 2;
    int[] dp = new int[27];
    Arrays.fill(dp, INF);
    dp[26] = 0;
    for (int i = 1; i < word.length(); i++) {
        int prev = word.charAt(i - 1) - 'A', cur = word.charAt(i) - 'A';
        int[] nxt = new int[27];
        Arrays.fill(nxt, INF);
        for (int o = 0; o < 27; o++) {
            if (dp[o] == INF) continue;
            nxt[o] = Math.min(nxt[o], dp[o] + keyDistance(prev, cur));
            nxt[prev] = Math.min(nxt[prev], dp[o] + keyDistance(o, cur));
        }
        dp = nxt;
    }
    int best = INF;
    for (int v : dp) best = Math.min(best, v);
    return best;
}

C++

int keyDistance(int a, int b) {
    if (a == 26) return 0;
    return abs(a / 6 - b / 6) + abs(a % 6 - b % 6);
}

int minimumDistance(string word) {
    const int INF = INT_MAX / 2;
    vector<int> dp(27, INF);
    dp[26] = 0;
    for (size_t i = 1; i < word.size(); i++) {
        int prev = word[i - 1] - 'A', cur = word[i] - 'A';
        vector<int> nxt(27, INF);
        for (int o = 0; o < 27; o++) {
            if (dp[o] == INF) continue;
            nxt[o] = min(nxt[o], dp[o] + keyDistance(prev, cur));
            nxt[prev] = min(nxt[prev], dp[o] + keyDistance(o, cur));
        }
        dp = nxt;
    }
    return *min_element(dp.begin(), dp.end());
}

JavaScript

var minimumDistance = function(word) {
    var dist = function(a, b) {
        if (a === 26) return 0;
        return Math.abs(Math.floor(a / 6) - Math.floor(b / 6)) + Math.abs(a % 6 - b % 6);
    };
    var INF = 1e9;
    var dp = new Array(27).fill(INF);
    dp[26] = 0;
    for (var i = 1; i < word.length; i++) {
        var prev = word.charCodeAt(i - 1) - 65, cur = word.charCodeAt(i) - 65;
        var nxt = new Array(27).fill(INF);
        for (var o = 0; o < 27; o++) {
            if (dp[o] === INF) continue;
            nxt[o] = Math.min(nxt[o], dp[o] + dist(prev, cur));
            nxt[prev] = Math.min(nxt[prev], dp[o] + dist(o, cur));
        }
        dp = nxt;
    }
    return Math.min.apply(null, dp);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming