Dijkstra - key observations and java impl
Observations\n  - cost of moving a finger is 0 for the first move, then manhattan distance b/w positions\n\n  - finding the min overall cost can be formulated a
### Observations\n  - cost of moving a finger is 0 for the first move, then manhattan distance b/w positions\n\n  - finding the min overall cost can be formulated as **shortest path on a DAG**\n    - graph vertex models a typing state with 3 identifying attributes \n        1. Index in the word\n        2. Left finger position\n        3. Right finger position\n        4. (non-identifying attribute) min cost of reaching the state\n        \n    - directed edges lead to a next vertex with index+1 and new position of either left or right finger\n        - edge weight is a move cost\n        - typical vertex will have 2 outbound edges, one for each finger\n    - weare looking for a lenght of a shortest path "start" to a vertex with word index == word.length()\n\nSince edge weights are non-negative, Dijkstra algo applies. As a side note, DP solutions can often be seen as a Bellman-Ford application to this graph.\n\nSpace optimization:\n  - states are symmetric w/respect to left & right fingers\n\t  - i.e. `(index, leftPosition, rightPosition)` is the same as `(index, rightPosition, leftPosition)`\n  - thus we can only consider states in the form of (index, smallerIdx, largerIdx)\n\n===========================\n\n### Time & Space complexity\n\n- Let `N` be a word length\n- for each `i = 0..N` there are at most `|alphabet|` vertices for left finger and same number for right finger\n- at least one of the fingers will be fixed at `word.charAt(i)`\n- thus total number of vertices is `O(N*|alphabet|)`\n- each vertex has at most `|alphabet|` incoming edges. Thus total amount of edges is `O(N*|alphabet|^2)`\n\nThen, given the implementation below:\nTC: `O(N*|alphabet|^2 * log(N*|alphabet|))`\nSC: `O(N*|alphabet|^2)`\n\nIf we assume constant size of the alphabet, then:\nTC: `O(N*log(N))`\nSC: `O(N)`\n\n\n```\nclass Solution {\n    private static final int NOWHERE = -1;\n    private static final int[] ROW_OF = new int[26];\n    private static final int[] COL_OF = new int[26];\n\n    static {\n        initPositions();\n    }\n\n    private static final void initPositions() {\n        for(int charIdx = 0; charIdx <= \'Z\' - \'A\'; charIdx++) {\n            int row = charIdx / 6;\n            int col = charIdx % 6;\n            ROW_OF[charIdx] = row;\n            COL_OF[charIdx] = col;\n        }\n    }\n\n    public int minimumDistance(String word) {\n\n        HashSet<Vertex> visited = new HashSet<>();\n        PriorityQueue<Vertex> minHeap = new PriorityQueue<>((v1, v2) -> v1.costToReach - v2.costToReach);\n\n        Vertex start = new Vertex(0, NOWHERE, NOWHERE, 0);\n        minHeap.offer(start);\n\n        while(!minHeap.isEmpty()) {\n            Vertex vertex = minHeap.poll();\n            if(!visited.add(vertex))\n                continue;\n\n            if(vertex.wordIdx == word.length())\n                return vertex.costToReach;\n\n            int nextPos = word.charAt(vertex.wordIdx) - \'A\';\n\n            Vertex nextWithLeftFinger = new Vertex(\n                vertex.wordIdx + 1, \n                nextPos, \n                vertex.rightPos, \n                vertex.costToReach + manhattanDistance(vertex.leftPos, nextPos)\n            );\n            \n            Vertex nextWithRightFinger = new Vertex(\n                vertex.wordIdx + 1, \n                vertex.leftPos, \n                nextPos,\n                vertex.costToReach + manhattanDistance(vertex.rightPos, nextPos)\n            );\n            minHeap.offer(nextWithLeftFinger);\n            minHeap.offer(nextWithRightFinger);\n        }\n\n        throw new IllegalStateException("Should not have reached here");\n    }\n\n    private static int manhattanDistance(int fromPos, int toPos) {\n        if(fromPos == NOWHERE)\n            return 0;\n        return Math.abs(ROW_OF[toPos] - ROW_OF[fromPos]) \n            + Math.abs(COL_OF[toPos] - COL_OF[fromPos]);\n    }\n\n    private static final class Vertex {\n        private final int wordIdx;\n        private final int leftPos;\n        private final int rightPos;\n        private final int costToReach;\n\n        private Vertex(int wordIdx, int leftPos, int rightPos, int costToReach) {\n            this.wordIdx = wordIdx;\n            this.leftPos = Math.min(leftPos, rightPos);\n            this.rightPos = Math.max(leftPos, rightPos);\n            this.costToReach = costToReach;\n        }\n\n        public boolean equals(Object o) {\n            // simplified. Cost is not accounted for equality & hash code\n            Vertex other = (Vertex) o;\n            return wordIdx == other.wordIdx && leftPos == other.leftPos && rightPos == other.rightPos;\n        }\n\n        public int hashCode() {\n            return Objects.hash(wordIdx, leftPos, rightPos);\n        }\n\n    }\n}\n```
[]