LeetCode Entry

1320. Minimum Distance to Type a Word Using Two Fingers

12.04.2026 hard 2026 kotlin rust

Min travel on keyboard to type a word

1320. Minimum Distance to Type a Word Using Two Fingers hard substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1326

Problem TLDR

Min travel on keyboard to type a word #hard #dp

Intuition

    // len is 300, table = 26
    // two fingers
    // travel finger 1 + travel finger 2
    //
    // HAPPY
    // 11221
    // can be dp i, f1, f2 = dist 300*26^2
    // should work
    // 11 minute, 45/55 test case wrong answer 294 vs 295 expected
    // mine is better means my algo cheats
    //

Top down dp is accepted. (position, finger1, finger2)

The clever intuition:

• at each step we have a situation: current target is w[i], one finger definitely at w[i-1], search for the other finger
• dp[a] is how much maximum we saved using extra finger finally placed at a
• dp[b] = max(A..Z -travel(a,c) +travel(b,c) + dp[a]), this finger ‘saves’ us from travel(bc) and makes us travel(ac)
• we store in dp[b] because we place finger on c and c became b at the next step

Approach

• write top down, its ok

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 35ms
    fun t(a: Char, b: Char) = abs((a-'A')%6-(b-'A')%6) + abs((a-'A')/6-(b-'A')/6)
    fun minimumDistance(w: String) = w.zipWithNext(::t).sum() -
        w.zipWithNext().fold(IntArray(26)) { dp, (b,c) ->
            dp[b-'A'] = ('A'..'Z').maxOf { dp[it-'A'] - t(it,c) } + t(b,c); dp
        }.max()

// 0ms
    pub fn minimum_distance(w: String) -> i32 {
        fn t(a: i32, b: i32) -> i32 { (a%6-b%6).abs() + (a/6-b/6).abs() }
        let (s, m) = w.bytes().map(|b|(b-b'A') as i32).tuple_windows().fold((0,[0;26]), |(s, mut dp), (b,c)| {
            dp[b as usize] = (0..26).map(|a| dp[a as usize]-t(a,c)).max().unwrap() + t(b,c); (s + t(b,c), dp)
        }); s - m.into_iter().max().unwrap()
    }