LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers Solution

Master LeetCode problem 1320 (Minimum Distance to Type a Word Using Two Fingers), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1320. Minimum Distance to Type a Word Using Two Fingers

Hard

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to keep track of the minimum cost of typing the word up to each position with each finger. We will iterate through the word and calculate the cost of typing each letter with either finger. At each step, we will update the minimum cost for each finger based on the previous positions and the distance to the current letter. The final answer will be the minimum cost of typing the entire word with two fingers.

Time Complexity: O(n^2), where n is the length of the word Space Complexity: O(n)

Solution Code

class Solution {
    public int minimumDistance(String word) {
        int n = word.length();
        int[][] dp = new int[n][27]; // 26 letters + 1 for not using the second finger
        
        for (int i = 1; i < n; i++) {
            int d = word.charAt(i) - 'A';
            for (int j = 0; j < 27; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + distance(j, d), dp[i - 1][d] + distance(j, word.charAt(i - 1) - 'A'));
            }
        }
        
        int minDist = Integer.MAX_VALUE;
        for (int j = 0; j < 27; j++) {
            minDist = Math.min(minDist, dp[n - 1][j]);
        }
        
        return minDist;
    }
    
    private int distance(int a, int b) {
        if (a == 26) return 0;
        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1320 (Minimum Distance to Type a Word Using Two Fingers)?

This page provides optimized solutions for LeetCode problem 1320 (Minimum Distance to Type a Word Using Two Fingers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1320 (Minimum Distance to Type a Word Using Two Fingers)?

The time complexity for LeetCode 1320 (Minimum Distance to Type a Word Using Two Fingers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1320 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1320 in Java, C++, or Python.

Back to LeetCode Solutions