💥💥C# | 100% beat on runtime and memory [EXPLAINED]
Intuition\nThe goal is to determine the minimum distance required to type a word using two fingers on a keyboard laid out in a grid. Each letter is at a specifi
# Intuition\nThe goal is to determine the minimum distance required to type a word using two fingers on a keyboard laid out in a grid. Each letter is at a specific coordinate, and the distance between two letters is calculated using the Manhattan distance formula. This means that you can only move up, down, left, or right.\n\n\n# Approach\nCoordinate Mapping: First, map each letter (A-Z) to its corresponding coordinates on the keyboard.\n\n\nDynamic Programming: Use a recursive function with memoization to calculate the minimum distance. The function tracks:\n\n\nThe current letter being typed.\nThe positions of both fingers.\n\n\nBase Case: If all letters are typed, return a distance of 0.\nRecursive Steps: For each letter, calculate the distance if either finger moves to that letter. Then, recursively calculate the distance for the next letter. Store results to avoid recalculating the same state.\n\n\n# Complexity\n- Time complexity:\nO(n\u22C527\u22C527), where n is the length of the word. The 27 represents the 26 letters plus an additional state for unoccupied fingers.\n\n- Space complexity:\nO(n\u22C527\u22C527) due to the memoization array storing results for all combinations of states.\n\n# Code\n```csharp []\npublic class Solution\n{\n    private readonly int[,] coordinates = new int[26, 2];\n\n    public Solution()\n    {\n        // Set up the coordinates for each letter A-Z\n        int index = 0;\n        for (int x = 0; x < 5; x++)\n        {\n            for (int y = 0; y < 6; y++)\n            {\n                if (index < 26)\n                {\n                    coordinates[index, 0] = x; // x-coordinate\n                    coordinates[index, 1] = y; // y-coordinate\n                    index++;\n                }\n            }\n        }\n    }\n\n    public int MinimumDistance(string word)\n    {\n        int[,,] memo = new int[word.Length, 27, 27];\n        for (int i = 0; i < word.Length; i++)\n            for (int j = 0; j < 27; j++)\n                for (int k = 0; k < 27; k++)\n                    memo[i, j, k] = -1; // Initialize memoization array\n\n        return Helper(word, 0, -1, -1, memo);\n    }\n\n    private int Helper(string word, int index, int pos1, int pos2, int[,,] memo)\n    {\n        if (index == word.Length) return 0; // End of the word\n        if (memo[index, pos1 + 1, pos2 + 1] != -1) return memo[index, pos1 + 1, pos2 + 1];\n\n        int letterIndex = word[index] - \'A\';\n        int distance1 = CalculateDistance(pos1, letterIndex);\n        int distance2 = CalculateDistance(pos2, letterIndex);\n\n        // Move finger 1 or finger 2 to the current letter\n        int option1 = distance1 + Helper(word, index + 1, letterIndex, pos2, memo);\n        int option2 = distance2 + Helper(word, index + 1, pos1, letterIndex, memo);\n\n        memo[index, pos1 + 1, pos2 + 1] = (option1 < option2) ? option1 : option2;\n        return memo[index, pos1 + 1, pos2 + 1];\n    }\n\n    private int CalculateDistance(int finger, int letterIndex)\n    {\n        if (finger == -1) return 0; // Starting position\n        return Math.Abs(coordinates[finger, 0] - coordinates[letterIndex, 0]) +\n               Math.Abs(coordinates[finger, 1] - coordinates[letterIndex, 1]);\n    }\n}\n\n```
['C#']