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 <= 300word consists of uppercase English letters
Hints for Minimum Distance to Type a Word Using Two Fingers
Hint 1
After typing
word[i], one finger is certainly resting onword[i]. What else do you need to know?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.
Hint 3
Let
dp[o]be the least cost so far with the other finger on keyo(26 = unused). For the next letter, either the finger onword[i]moves (ounchanged) or the other finger moves fromo(free if unused) and the old finger becomes the 'other' one, resting onword[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
- Let
dist(a, b)be the grid distance, withdist(26, b) = 0for an unused finger. - Start with
dp[26] = 0after the first letter (typed by one finger for free) and every otherdpvalue infinite. - For each next letter
curwith previous letterprev, buildnext: for every finitedp[o], setnext[o] = min(next[o], dp[o] + dist(prev, cur))(the finger onprevtypescur) andnext[prev] = min(next[prev], dp[o] + dist(o, cur))(the other finger typescur). - 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
prevbecomes the new 'other' finger atprev. - Letter
iis at rowi / 6and columni % 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