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:
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.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:
i = 0 and shift s[0] 25 times to the previous character for a total cost of 1.i = 1 and shift s[1] 25 times to the next character for a total cost of 0.i = 2 and shift s[2] 25 times to the previous character for a total cost of 1.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:
i = 0 and shift s[0] 9 times to the previous character for a total cost of 9.i = 1 and shift s[1] 10 times to the next character for a total cost of 10.i = 2 and shift s[2] 1 time to the previous character for a total cost of 1.i = 3 and shift s[3] 11 times to the next character for a total cost of 11.Constraints:
1 <= s.length == t.length <= 105s and t consist only of lowercase English letters.nextCost.length == previousCost.length == 260 <= nextCost[i], previousCost[i] <= 109In #3361 Shift Distance Between Two Strings, the task is to determine the minimum cost required to transform one string into another by shifting characters across the alphabet. Each shift may have a specific cost, and the alphabet behaves like a circular structure, meaning you can move forward or backward between characters.
A common strategy is to treat the alphabet as a cyclic array. For each character pair in the same position of the two strings, compute the cost of shifting clockwise and counterclockwise. To make these computations efficient, you can precompute cumulative costs (prefix sums) for the alphabet. This allows constant-time queries for the cost of moving between two letters in either direction.
Iterate through the strings, calculate both possible shift costs for each character, and accumulate the minimum. Since the alphabet size is fixed, preprocessing remains small while the main traversal depends on the string length.
The optimized approach runs in O(n) time for a string of length n, with O(1) additional space aside from small auxiliary arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix sum + cyclic shift calculation | O(n) | O(1) |
| Direct per-character shift evaluation | O(n) | O(1) |
Back To Back SWE
Use these hints if you're stuck. Try solving on your own first.
- For every unordered pair of characters <code>(a, b)</code>, the cost of turning <code>a</code> into <code>b</code> is equal to the minimum between: <ul> <li>If <code>i < j</code>, <code>nextCost[i] + nextCost[i + 1] + … + nextCost[j - 1]</code>, and <code>nextCost[i] + nextCost[i + 1] + … + nextCost[25] + nextCost[0] + … + nextCost[j - 1]</code> otherwise.</li> <li>If <code>i < j</code>, <code>prevCost[i] + prevCost[i - 1] + … + prevCost[0] + prevCost[25] + … + prevCost[j + 1]</code>, and <code>prevCost[i] + prevCost[i - 1] + … + prevCost[j + 1]</code> otherwise.</li> </ul> Where <code>i</code> and <code>j</code> are the indices of <code>a</code> and <code>b</code> in the alphabet.
The shift distance is the sum of costs of turning <code>s[i]</code> into <code>t[i]</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, problems like this appear in technical interviews because they combine string manipulation, prefix sums, and optimization. Interviewers often use such questions to evaluate problem modeling and handling cyclic structures. It is particularly relevant for mid-level algorithm rounds.
Prefix sum arrays are typically used to store cumulative shift costs across the alphabet. Since the alphabet size is fixed, these arrays allow fast cost lookups for any shift range. This makes each character comparison efficient during the main iteration.
The optimal approach models the alphabet as a circular structure and computes the cost of shifting characters in both clockwise and counterclockwise directions. Using prefix sums for shift costs allows constant-time calculations for each character pair. This results in an overall O(n) solution.
Shifting characters can wrap around from 'z' to 'a' or vice versa, making the alphabet behave like a cycle. Treating it as circular ensures that both forward and backward transitions are considered correctly. This helps in finding the minimum shift cost between characters.