# Shift Distance Between Two Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shift-distance-between-two-strings)
Canonical: https://scaleengineer.com/dsa/problems/shift-distance-between-two-strings
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
---
## Problem
You are given two strings `s` and `t` of the same length, and two integer arrays `nextCost` and `previousCost`.

In one operation, you can pick any index `i` of `s`, and perform **either one** of the following actions:

* Shift `s[i]` to the next letter in the alphabet. If `s[i] == 'z'`, you should replace it with `'a'`. This operation costs `nextCost[j]` where `j` is the index of `s[i]` in the alphabet.
* Shift `s[i]` to the previous letter in the alphabet. If `s[i] == 'a'`, you should replace it with `'z'`. This operation costs `previousCost[j]` where `j` is the index of `s[i]` in the alphabet.

The **shift distance** is the **minimum** total cost of operations required to transform `s` into `t`.

Return the **shift distance** from `s` to `t`.

**Example 1:**

**Input:** s = "abab", t = "baba", nextCost = \[100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\], previousCost = \[1,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\]

**Output:** 2

**Explanation:**

* We choose index `i = 0` and shift `s[0]` 25 times to the previous character for a total cost of 1.
* We choose index `i = 1` and shift `s[1]` 25 times to the next character for a total cost of 0.
* We choose index `i = 2` and shift `s[2]` 25 times to the previous character for a total cost of 1.
* We choose index `i = 3` and shift `s[3]` 25 times to the next character for a total cost of 0.

**Example 2:**

**Input:** s = "leet", t = "code", nextCost = \[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1\], previousCost = \[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1\]

**Output:** 31

**Explanation:**

* We choose index `i = 0` and shift `s[0]` 9 times to the previous character for a total cost of 9.
* We choose index `i = 1` and shift `s[1]` 10 times to the next character for a total cost of 10.
* We choose index `i = 2` and shift `s[2]` 1 time to the previous character for a total cost of 1.
* We choose index `i = 3` and shift `s[3]` 11 times to the next character for a total cost of 11.

**Constraints:**

* `1 <= s.length == t.length <= 105`
* `s` and `t` consist only of lowercase English letters.
* `nextCost.length == previousCost.length == 26`
* `0 <= nextCost[i], previousCost[i] <= 109`

# Approaches
## Brute-Force: Dijkstra for Each Character Pair
This approach treats the transformation of each character `s[i]` to `t[i]` as an independent subproblem. The total shift distance is the sum of the minimum costs for each of these transformations. We can model the 26 letters of the alphabet as a graph where each letter is a node. From each node (character), there are directed edges to the next and previous letters, with weights defined by `nextCost` and `previousCost`. The problem then becomes finding the shortest path from character `s[i]` to `t[i]` on this graph. Since edge weights are non-negative, Dijkstra's algorithm is a suitable choice. For every single character pair in the input strings, we execute a full run of Dijkstra's algorithm.
**Time:** O(N * A log A), where N is the length of the strings and A is the size of the alphabet (26). Dijkstra's algorithm takes O(E log V) = O(A log A) time, and we run it N times. · **Space:** O(A), where A is the size of the alphabet (26). This space is used by Dijkstra's algorithm for the distance array and the priority queue.
**Pros:** Conceptually straightforward and easy to implement.; Correctly solves the problem for small inputs.
**Cons:** Highly inefficient due to redundant computations. If the same character transformation (e.g., 'a' to 'c') appears multiple times in the input strings, Dijkstra's algorithm is run from scratch each time.; This approach is very likely to exceed the time limit for larger inputs.
### Explanation
For each index `i` from 0 to the length of the string, we want to find the minimum cost to change `s[i]` to `t[i]`. This is a classic shortest path problem on a graph. We can imagine a graph with 26 nodes, representing 'a' through 'z'. From any node `c`, we can move to the next character with cost `nextCost[c - 'a']` or the previous character with cost `previousCost[c - 'a']`. The alphabet wraps around, so 'z' moves to 'a' and 'a' moves to 'z'.

This brute-force method calculates this shortest path for every `i`. It iterates through the strings, and for each `(s[i], t[i])` pair, it runs Dijkstra's algorithm to find the minimum cost. The total cost is the accumulation of these individual minimum costs.

```java
class Solution {
    public long getShiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        long totalDistance = 0;
        for (int i = 0; i < s.length(); i++) {
            int start = s.charAt(i) - 'a';
            int end = t.charAt(i) - 'a';
            totalDistance += dijkstra(start, end, nextCost, previousCost);
        }
        return totalDistance;
    }

    private long dijkstra(int startNode, int endNode, int[] nextCost, int[] previousCost) {
        if (startNode == endNode) return 0;
        int ALPHABET_SIZE = 26;
        long[] dist = new long[ALPHABET_SIZE];
        java.util.Arrays.fill(dist, Long.MAX_VALUE);
        dist[startNode] = 0;

        java.util.PriorityQueue<long[]> pq = new java.util.PriorityQueue<>(java.util.Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, startNode});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentCost = current[0];
            int u = (int) current[1];

            if (u == endNode) {
                return currentCost;
            }

            if (currentCost > dist[u]) {
                continue;
            }

            // Move to next character
            int v_next = (u + 1) % ALPHABET_SIZE;
            long costToNext = nextCost[u];
            if (dist[u] + costToNext < dist[v_next]) {
                dist[v_next] = dist[u] + costToNext;
                pq.offer(new long[]{dist[v_next], v_next});
            }

            // Move to previous character
            int v_prev = (u - 1 + ALPHABET_SIZE) % ALPHABET_SIZE;
            long costToPrev = previousCost[u];
            if (dist[u] + costToPrev < dist[v_prev]) {
                dist[v_prev] = dist[u] + costToPrev;
                pq.offer(new long[]{dist[v_prev], v_prev});
            }
        }
        return dist[endNode]; // Should be found earlier
    }
}
```
### Algorithm
- The core idea is to calculate the minimum cost to transform `s[i]` to `t[i]` for each index `i` and sum these costs up.
- The problem of transforming one character to another can be modeled as a shortest path problem on a graph.
- **Graph Representation**:
  - The 26 lowercase English letters are the nodes of the graph (0 to 25).
  - For each character `c` (node `u`), there are two outgoing directed edges:
    1. An edge to the next character `(u + 1) % 26` with a weight of `nextCost[u]`.
    2. An edge to the previous character `(u - 1 + 26) % 26` with a weight of `previousCost[u]`.
- **Algorithm Steps**:
  1. Initialize a variable `totalCost` to 0.
  2. Iterate through the strings `s` and `t` from `i = 0` to `s.length() - 1`.
  3. For each pair of characters `s[i]` and `t[i]`, determine their corresponding alphabet indices, `startNode` and `endNode`.
  4. If `startNode` is the same as `endNode`, the cost is 0.
  5. Otherwise, run Dijkstra's algorithm on the alphabet graph to find the shortest path cost from `startNode` to `endNode`.
  6. Add this computed cost to `totalCost`.
  7. After the loop finishes, return `totalCost`.

## Memoization with Dijkstra
To optimize the brute-force approach, we can use memoization (a form of dynamic programming) to store the results of our shortest path calculations. We create a 2D array, say `memo[26][26]`, to hold the minimum cost of transforming any character to another. When we need to find the cost for a pair `(s[i], t[i])`, we first check if we have already computed it. If `memo[s[i]-'a'][t[i]-'a']` has a stored value, we use it directly. Otherwise, we run Dijkstra's algorithm, and before returning the result, we store it in the memo table for future use. This prevents us from solving the same subproblem multiple times.
**Time:** O(min(N, A^2) * A log A + N). We run Dijkstra at most `min(N, A^2)` times, which is the number of unique `(s[i], t[i])` pairs. Then we iterate through the string of length N. · **Space:** O(A^2), where A is the alphabet size. This is for the memoization table.
**Pros:** Much more efficient than the naive approach for strings with repeating character pairs.; Avoids redundant computations.
**Cons:** Requires extra space for the memoization table.; In the worst-case scenario where all possible 26*26 character pairs are queried, the performance is worse than precomputation with Floyd-Warshall due to the overhead of repeated Dijkstra initializations and priority queue operations.
### Explanation
This method enhances the previous approach by adding a cache. The number of unique character transformation pairs is at most 26 * 26 = 676. For a long string, it's highly likely that we will need to compute the same transformation cost multiple times. By storing the result after the first computation, we can retrieve it in O(1) time for all subsequent requests.

A 2D array `memo[26][26]` acts as our cache. Each time we need the cost from a `start` character to an `end` character, we first look it up in `memo`. If a value exists, we use it. If not, we perform the Dijkstra calculation, store the result in `memo`, and then use it. This ensures that Dijkstra's algorithm is run at most once for each unique pair of characters.

```java
class Solution {
    private long[][] memo;
    private int[] nextCost;
    private int[] previousCost;
    private final int ALPHABET_SIZE = 26;

    public long getShiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        this.memo = new long[ALPHABET_SIZE][ALPHABET_SIZE];
        for (long[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        this.nextCost = nextCost;
        this.previousCost = previousCost;

        long totalDistance = 0;
        for (int i = 0; i < s.length(); i++) {
            int start = s.charAt(i) - 'a';
            int end = t.charAt(i) - 'a';
            totalDistance += getMinCost(start, end);
        }
        return totalDistance;
    }

    private long getMinCost(int startNode, int endNode) {
        if (startNode == endNode) return 0;
        if (memo[startNode][endNode] != -1) {
            return memo[startNode][endNode];
        }

        // Dijkstra's algorithm to find the shortest path
        long cost = dijkstra(startNode, endNode);
        memo[startNode][endNode] = cost;
        return cost;
    }

    private long dijkstra(int startNode, int endNode) {
        // ... Full Dijkstra implementation as in the previous approach ...
        // This function would calculate and return the shortest path cost.
        // For brevity, the implementation is omitted here.
        long[] dist = new long[ALPHABET_SIZE];
        java.util.Arrays.fill(dist, Long.MAX_VALUE);
        dist[startNode] = 0;
        java.util.PriorityQueue<long[]> pq = new java.util.PriorityQueue<>(java.util.Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, startNode});
        while(!pq.isEmpty()) {
            long[] curr = pq.poll();
            long cost = curr[0];
            int u = (int)curr[1];
            if (u == endNode) return cost;
            if (cost > dist[u]) continue;
            // ... neighbor logic ...
        }
        return -1; // Should not happen
    }
}
```
### Algorithm
- This approach builds upon the previous one by avoiding re-computation.
- A 2D array, `memo[26][26]`, is used to cache the shortest path costs.
- **Algorithm Steps**:
  1. Initialize a `memo` table of size `26x26` with a sentinel value (e.g., -1) to indicate that a path cost has not been computed yet.
  2. Initialize `totalCost` to 0.
  3. Iterate through the strings `s` and `t` from `i = 0` to `s.length() - 1`.
  4. Get the `startNode` and `endNode` for `s[i]` and `t[i]`.
  5. Check `memo[startNode][endNode]`. If it contains a valid cost, add it to `totalCost`.
  6. If the cost is not in the memo table, run Dijkstra's algorithm to compute it.
  7. Store the newly computed cost in `memo[startNode][endNode]`.
  8. Add the cost to `totalCost`.
  9. Return `totalCost`.

## Precomputation using Floyd-Warshall Algorithm
Instead of computing costs lazily as needed, we can precompute all of them upfront. The problem requires finding the shortest paths between all pairs of characters. The Floyd-Warshall algorithm is designed for exactly this: finding all-pairs shortest paths. We first build a `26x26` adjacency matrix representing the initial costs for single shifts. Then, we apply the Floyd-Warshall algorithm, which iteratively considers each character as an intermediate point in paths between other characters, to find the overall minimum costs. After this `O(A^3)` precomputation step, the cost for any transformation `s[i] -> t[i]` is a simple `O(1)` lookup in our computed distance matrix. The total cost is then found by summing these lookup values over the entire string.
**Time:** O(A^3 + N). The precomputation with Floyd-Warshall takes O(A^3), and the final summation takes O(N). Since A is a small constant (26), this is very efficient. · **Space:** O(A^2) for the distance matrix.
**Pros:** Efficient for the given constraints, as the precomputation cost is constant with respect to the input string length N.; Simple to implement with three nested loops.; Separates the graph logic (precomputation) from the main problem logic (summation).
**Cons:** The time complexity of the precomputation step, O(A^3), can be slow if the alphabet size A were much larger.; It is slightly less efficient than running Dijkstra from each node for this specific problem.
### Explanation
The Floyd-Warshall algorithm is a dynamic programming approach to solve the all-pairs shortest path problem. It works by iterating through all possible intermediate vertices for each pair of source and destination vertices.

The algorithm is as follows:
1.  Create a `dist[A][A]` matrix, where `A=26`. Initialize it with the direct edge weights from the alphabet graph. `dist[i][j]` will store the shortest distance from `i` to `j` found so far.
2.  Use three nested loops: `for k from 0 to A-1`, `for i from 0 to A-1`, `for j from 0 to A-1`. Inside the loops, update the shortest path from `i` to `j` by checking if going through `k` is shorter: `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`.
3.  After the loops complete, `dist[i][j]` holds the absolute minimum cost to transform character `i` to character `j`.
4.  Finally, iterate through the input strings `s` and `t` and sum up the costs `dist[s[i]-'a'][t[i]-'a']` to get the final answer.

```java
class Solution {
    public long getShiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        int ALPHABET_SIZE = 26;
        long[][] dist = new long[ALPHABET_SIZE][ALPHABET_SIZE];

        // Initialize distance matrix for Floyd-Warshall
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            java.util.Arrays.fill(dist[i], Long.MAX_VALUE / 2); // Use large value to prevent overflow
            dist[i][i] = 0;
        }

        for (int i = 0; i < ALPHABET_SIZE; i++) {
            dist[i][(i + 1) % ALPHABET_SIZE] = Math.min(dist[i][(i + 1) % ALPHABET_SIZE], (long)nextCost[i]);
            dist[i][(i - 1 + ALPHABET_SIZE) % ALPHABET_SIZE] = Math.min(dist[i][(i - 1 + ALPHABET_SIZE) % ALPHABET_SIZE], (long)previousCost[i]);
        }

        // Floyd-Warshall algorithm
        for (int k = 0; k < ALPHABET_SIZE; k++) {
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                for (int j = 0; j < ALPHABET_SIZE; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        // Calculate total distance using the precomputed costs
        long totalDistance = 0;
        for (int i = 0; i < s.length(); i++) {
            int startCharIndex = s.charAt(i) - 'a';
            int targetCharIndex = t.charAt(i) - 'a';
            totalDistance += dist[startCharIndex][targetCharIndex];
        }

        return totalDistance;
    }
}
```
### Algorithm
- This approach precomputes all possible transformation costs before processing the input strings.
- It uses the Floyd-Warshall algorithm, a classic algorithm for finding all-pairs shortest paths (APSP) in a weighted directed graph.
- **Algorithm Steps**:
  1. **Preprocessing**:
     - Create a 2D distance matrix `dist[26][26]`.
     - Initialize `dist[i][i] = 0`, `dist[i][j] = infinity` for `i != j`.
     - For each node `i`, set `dist[i][(i+1)%26] = nextCost[i]` and `dist[i][(i-1+26)%26] = previousCost[i]`.
     - Run the Floyd-Warshall algorithm with three nested loops (`k`, `i`, `j`) to update `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`.
  2. **Calculation**:
     - Initialize `totalCost = 0`.
     - Iterate through the strings `s` and `t`.
     - For each `i`, find `start = s[i] - 'a'` and `end = t[i] - 'a'`.
     - Add the precomputed `dist[start][end]` to `totalCost`.
  3. Return `totalCost`.

## Optimized Precomputation using Dijkstra from Each Node
This approach also relies on precomputing all-pairs shortest paths but uses a more efficient algorithm for this task. For a graph with `V` vertices and `E` edges with non-negative weights, we can find all-pairs shortest paths by running Dijkstra's algorithm `V` times, once from each vertex. The complexity of this is `V * O(E log V)`. In our case, `V=A=26` and `E=2A=52`, so the precomputation complexity is `A * O(A log A) = O(A^2 log A)`. This is asymptotically better than Floyd-Warshall's `O(A^3)`. After the `minCosts` table is populated, the rest of the logic is the same: a single pass over the input strings to sum up the costs.
**Time:** O(A^2 log A + N). The precomputation involves running Dijkstra (O(A log A)) for each of the A nodes. The final summation is O(N). · **Space:** O(A^2) for the `minCosts` matrix.
**Pros:** The most efficient approach in terms of time complexity.; The expensive precomputation step is independent of the input string length N, making it ideal for scenarios with long strings.
**Cons:** The implementation is slightly more complex than Floyd-Warshall, as it involves managing a priority queue within a loop.
### Explanation
The key insight here is that for sparse graphs (where E is much smaller than V^2) or even for dense graphs, running Dijkstra from every node is often faster than Floyd-Warshall. Our alphabet graph is sparse (`E = 2A`), making this approach particularly effective.

The process is as follows:
1.  Create a `minCosts[A][A]` matrix to store the final results.
2.  Loop through each character `i` from 0 to 25, treating it as the `startNode`.
3.  Inside the loop, run a full Dijkstra's algorithm starting from `i`. This will compute the shortest path from `i` to every other node `j`.
4.  Store the computed distances in the `minCosts[i]` row.
5.  After the outer loop completes, the `minCosts` table is fully populated with all-pairs shortest paths.
6.  The final calculation is a linear scan through `s` and `t` to sum the costs looked up from the `minCosts` table.

```java
class Solution {
    public long getShiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        int ALPHABET_SIZE = 26;
        long[][] minCosts = new long[ALPHABET_SIZE][ALPHABET_SIZE];

        // Precomputation: Run Dijkstra from each node
        for (int startNode = 0; startNode < ALPHABET_SIZE; startNode++) {
            long[] dist = new long[ALPHABET_SIZE];
            java.util.Arrays.fill(dist, Long.MAX_VALUE);
            dist[startNode] = 0;

            java.util.PriorityQueue<long[]> pq = new java.util.PriorityQueue<>(java.util.Comparator.comparingLong(a -> a[0]));
            pq.offer(new long[]{0, startNode});

            while (!pq.isEmpty()) {
                long[] current = pq.poll();
                long currentCost = current[0];
                int u = (int) current[1];

                if (currentCost > dist[u]) {
                    continue;
                }

                // Move to next character
                int v_next = (u + 1) % ALPHABET_SIZE;
                long costToNext = nextCost[u];
                if (dist[u] + costToNext < dist[v_next]) {
                    dist[v_next] = dist[u] + costToNext;
                    pq.offer(new long[]{dist[v_next], v_next});
                }

                // Move to previous character
                int v_prev = (u - 1 + ALPHABET_SIZE) % ALPHABET_SIZE;
                long costToPrev = previousCost[u];
                if (dist[u] + costToPrev < dist[v_prev]) {
                    dist[v_prev] = dist[u] + costToPrev;
                    pq.offer(new long[]{dist[v_prev], v_prev});
                }
            }
            minCosts[startNode] = dist;
        }

        // Calculate total distance using the precomputed costs
        long totalDistance = 0;
        for (int i = 0; i < s.length(); i++) {
            int startCharIndex = s.charAt(i) - 'a';
            int targetCharIndex = t.charAt(i) - 'a';
            totalDistance += minCosts[startCharIndex][targetCharIndex];
        }

        return totalDistance;
    }
}
```
### Algorithm
- This is the most efficient approach. Like Floyd-Warshall, it precomputes all-pairs shortest paths, but with a better time complexity.
- For graphs with non-negative weights, running a single-source shortest path (SSSP) algorithm from each vertex is more efficient than Floyd-Warshall.
- **Algorithm Steps**:
  1. **Preprocessing**:
     - Create a 2D distance matrix `minCosts[26][26]`.
     - Iterate `startNode` from 0 to 25.
     - For each `startNode`, run Dijkstra's algorithm to find the shortest paths from `startNode` to all other 25 nodes.
     - Store the resulting array of distances in `minCosts[startNode]`.
  2. **Calculation**:
     - This step is identical to the Floyd-Warshall approach. Initialize `totalCost = 0`, iterate through the strings, and sum up the costs from the `minCosts` table.
  3. Return `totalCost`.

# Solutions
### Java

```java
class Solution {
public
  long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
    int m = 26;
    long[] s1 = new long[(m << 1) + 1];
    long[] s2 = new long[(m << 1) + 1];
    for (int i = 0; i < (m << 1); i++) {
      s1[i + 1] = s1[i] + nextCost[i % m];
      s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
    }
    long ans = 0;
    for (int i = 0; i < s.length(); i++) {
      int x = s.charAt(i) - 'a';
      int y = t.charAt(i) - 'a';
      long c1 = s1[y + (y < x ? m : 0)] - s1[x];
      long c2 = s2[x + (x < y ? m : 0)] - s2[y];
      ans += Math.min(c1, c2);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long shiftDistance(string s, string t, vector<int> &nextCost,
                          vector<int> &previousCost) {
    int m = 26;
    vector<long long> s1((m << 1) + 1);
    vector<long long> s2((m << 1) + 1);
    for (int i = 0; i < (m << 1); ++i) {
      s1[i + 1] = s1[i] + nextCost[i % m];
      s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
    }
    long long ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      int x = s[i] - 'a';
      int y = t[i] - 'a';
      long long c1 = s1[y + (y < x ? m : 0)] - s1[x];
      long long c2 = s2[x + (x < y ? m : 0)] - s2[y];
      ans += min(c1, c2);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shiftDistance(self, s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int: m = 26 s1 = [0] * (m << 1 | 1) s2 = [0] * (m << 1 | 1) for i in range(m << 1): s1[i + 1] = s1[i] + nextCost[i % m] s2[i + 1] = s2[i] + previousCost[(i + 1) % m] ans = 0 for a, b in zip(s, t): x, y = ord(a) - ord("a"), ord(b) - ord("a") c1 = s1[y + m if y < x else y] - s1[x] c2 = s2[x + m if x < y else x] - s2[y] ans += min(c1, c2) return ans

```