Shift Distance Between Two Strings
MedPrompt
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. Ifs[i] == 'z', you should replace it with'a'. This operation costsnextCost[j]wherejis the index ofs[i]in the alphabet. - Shift
s[i]to the previous letter in the alphabet. Ifs[i] == 'a', you should replace it with'z'. This operation costspreviousCost[j]wherejis the index ofs[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 = 0and shifts[0]25 times to the previous character for a total cost of 1. - We choose index
i = 1and shifts[1]25 times to the next character for a total cost of 0. - We choose index
i = 2and shifts[2]25 times to the previous character for a total cost of 1. - We choose index
i = 3and shifts[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 = 0and shifts[0]9 times to the previous character for a total cost of 9. - We choose index
i = 1and shifts[1]10 times to the next character for a total cost of 10. - We choose index
i = 2and shifts[2]1 time to the previous character for a total cost of 1. - We choose index
i = 3and shifts[3]11 times to the next character for a total cost of 11.
Constraints:
1 <= s.length == t.length <= 105sandtconsist only of lowercase English letters.nextCost.length == previousCost.length == 260 <= nextCost[i], previousCost[i] <= 109
Approaches
4 approaches with complexity analysis and trade-offs.
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.
Algorithm
- The core idea is to calculate the minimum cost to transform
s[i]tot[i]for each indexiand 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(nodeu), there are two outgoing directed edges:- An edge to the next character
(u + 1) % 26with a weight ofnextCost[u]. - An edge to the previous character
(u - 1 + 26) % 26with a weight ofpreviousCost[u].
- An edge to the next character
- Algorithm Steps:
- Initialize a variable
totalCostto 0. - Iterate through the strings
sandtfromi = 0tos.length() - 1. - For each pair of characters
s[i]andt[i], determine their corresponding alphabet indices,startNodeandendNode. - If
startNodeis the same asendNode, the cost is 0. - Otherwise, run Dijkstra's algorithm on the alphabet graph to find the shortest path cost from
startNodetoendNode. - Add this computed cost to
totalCost. - After the loop finishes, return
totalCost.
- Initialize a variable
Walkthrough
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.
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 }}Complexity
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.
Trade-offs
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.
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.
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:
- Initialize a
memotable of size26x26with a sentinel value (e.g., -1) to indicate that a path cost has not been computed yet. - Initialize
totalCostto 0. - Iterate through the strings
sandtfromi = 0tos.length() - 1. - Get the
startNodeandendNodefors[i]andt[i]. - Check
memo[startNode][endNode]. If it contains a valid cost, add it tototalCost. - If the cost is not in the memo table, run Dijkstra's algorithm to compute it.
- Store the newly computed cost in
memo[startNode][endNode]. - Add the cost to
totalCost. - Return
totalCost.
- Initialize a
Walkthrough
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.
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 }}Complexity
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.
Trade-offs
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.
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.
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:
- Preprocessing:
- Create a 2D distance matrix
dist[26][26]. - Initialize
dist[i][i] = 0,dist[i][j] = infinityfori != j. - For each node
i, setdist[i][(i+1)%26] = nextCost[i]anddist[i][(i-1+26)%26] = previousCost[i]. - Run the Floyd-Warshall algorithm with three nested loops (
k,i,j) to updatedist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
- Create a 2D distance matrix
- Calculation:
- Initialize
totalCost = 0. - Iterate through the strings
sandt. - For each
i, findstart = s[i] - 'a'andend = t[i] - 'a'. - Add the precomputed
dist[start][end]tototalCost.
- Initialize
- Return
totalCost.
- Preprocessing:
Walkthrough
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:
- Create a
dist[A][A]matrix, whereA=26. Initialize it with the direct edge weights from the alphabet graph.dist[i][j]will store the shortest distance fromitojfound so far. - 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 fromitojby checking if going throughkis shorter:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). - After the loops complete,
dist[i][j]holds the absolute minimum cost to transform characterito characterj. - Finally, iterate through the input strings
sandtand sum up the costsdist[s[i]-'a'][t[i]-'a']to get the final answer.
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; }}Complexity
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.
Trade-offs
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.
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.
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:
- Preprocessing:
- Create a 2D distance matrix
minCosts[26][26]. - Iterate
startNodefrom 0 to 25. - For each
startNode, run Dijkstra's algorithm to find the shortest paths fromstartNodeto all other 25 nodes. - Store the resulting array of distances in
minCosts[startNode].
- Create a 2D distance matrix
- Calculation:
- This step is identical to the Floyd-Warshall approach. Initialize
totalCost = 0, iterate through the strings, and sum up the costs from theminCoststable.
- This step is identical to the Floyd-Warshall approach. Initialize
- Return
totalCost.
- Preprocessing:
Walkthrough
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:
- Create a
minCosts[A][A]matrix to store the final results. - Loop through each character
ifrom 0 to 25, treating it as thestartNode. - Inside the loop, run a full Dijkstra's algorithm starting from
i. This will compute the shortest path fromito every other nodej. - Store the computed distances in the
minCosts[i]row. - After the outer loop completes, the
minCoststable is fully populated with all-pairs shortest paths. - The final calculation is a linear scan through
sandtto sum the costs looked up from theminCoststable.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.