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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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 <= 10^5
  • s and t consist only of lowercase English letters.
  • nextCost.length == previousCost.length == 26
  • 0 <= nextCost[i], previousCost[i] <= 10^9

Solution

Method 1 – Prefix Sum for Circular Shifts

Intuition

For each character, we can shift forward (next) or backward (previous) in the alphabet, wrapping around. The cost for each shift is given. For each position, we compute the cost to shift from s[i] to t[i] in both directions and take the minimum.

Approach

  1. For each character pair (s[i], t[i]):
    • Compute the forward distance (number of next shifts) and backward distance (number of previous shifts) in the alphabet.
    • For each, sum the costs using nextCost and previousCost arrays, using prefix sums for efficiency.
    • Take the minimum of the two costs and add to the total.
  2. Return the total cost.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        vector<long long> nextSum(27), prevSum(27);
        for (int i = 0; i < 26; ++i) {
            nextSum[i+1] = nextSum[i] + nextCost[i];
            prevSum[i+1] = prevSum[i] + previousCost[i];
        }
        long long ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            int a = s[i] - 'a', b = t[i] - 'a';
            int fwd = (b - a + 26) % 26, bwd = (a - b + 26) % 26;
            long long cost1 = nextSum[a+fwd] - nextSum[a];
            long long cost2 = prevSum[a+1] - prevSum[a-bwd+26];
            cost2 = prevSum[a+1] - prevSum[(a-bwd+26)%26];
            for (int j = 0, x = a; j < bwd; ++j) x = (x-1+26)%26, cost2 += previousCost[x];
            ans += min(cost1, cost2);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func shiftDistance(s, t string, nextCost, previousCost []int) int64 {
    n := len(s)
    nextSum := make([]int64, 27)
    prevSum := make([]int64, 27)
    for i := 0; i < 26; i++ {
        nextSum[i+1] = nextSum[i] + int64(nextCost[i])
        prevSum[i+1] = prevSum[i] + int64(previousCost[i])
    }
    var ans int64
    for i := 0; i < n; i++ {
        a := int(s[i] - 'a')
        b := int(t[i] - 'a')
        fwd := (b - a + 26) % 26
        bwd := (a - b + 26) % 26
        cost1 := nextSum[a+fwd] - nextSum[a]
        cost2 := int64(0)
        x := a
        for j := 0; j < bwd; j++ {
            x = (x - 1 + 26) % 26
            cost2 += int64(previousCost[x])
        }
        ans += cost1
        if cost2 < cost1 {
            ans = ans - cost1 + cost2
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        long[] nextSum = new long[27], prevSum = new long[27];
        for (int i = 0; i < 26; ++i) {
            nextSum[i+1] = nextSum[i] + nextCost[i];
            prevSum[i+1] = prevSum[i] + previousCost[i];
        }
        long ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            int a = s.charAt(i) - 'a', b = t.charAt(i) - 'a';
            int fwd = (b - a + 26) % 26, bwd = (a - b + 26) % 26;
            long cost1 = nextSum[a+fwd] - nextSum[a];
            long cost2 = 0;
            int x = a;
            for (int j = 0; j < bwd; ++j) {
                x = (x - 1 + 26) % 26;
                cost2 += previousCost[x];
            }
            ans += Math.min(cost1, cost2);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun shiftDistance(s: String, t: String, nextCost: IntArray, previousCost: IntArray): Long {
        val nextSum = LongArray(27)
        val prevSum = LongArray(27)
        for (i in 0 until 26) {
            nextSum[i+1] = nextSum[i] + nextCost[i]
            prevSum[i+1] = prevSum[i] + previousCost[i]
        }
        var ans = 0L
        for (i in s.indices) {
            val a = s[i] - 'a'
            val b = t[i] - 'a'
            val fwd = (b - a + 26) % 26
            val bwd = (a - b + 26) % 26
            val cost1 = nextSum[a+fwd] - nextSum[a]
            var cost2 = 0L
            var x = a
            repeat(bwd) {
                x = (x - 1 + 26) % 26
                cost2 += previousCost[x]
            }
            ans += minOf(cost1, cost2)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def shiftDistance(self, s: str, t: str, nextCost: list[int], previousCost: list[int]) -> int:
        ans = 0
        for a, b in zip(s, t):
            ai, bi = ord(a) - ord('a'), ord(b) - ord('a')
            fwd = (bi - ai) % 26
            bwd = (ai - bi) % 26
            cost1 = sum(nextCost[(ai + i) % 26] for i in range(fwd))
            cost2 = sum(previousCost[(ai - i - 1) % 26] for i in range(bwd))
            ans += min(cost1, cost2)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn shift_distance(s: String, t: String, next_cost: Vec<i32>, previous_cost: Vec<i32>) -> i64 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let mut ans = 0i64;
        for i in 0..s.len() {
            let a = (s[i] - b'a') as i32;
            let b = (t[i] - b'a') as i32;
            let fwd = (b - a + 26) % 26;
            let bwd = (a - b + 26) % 26;
            let mut cost1 = 0;
            for j in 0..fwd {
                cost1 += next_cost[((a + j) % 26) as usize] as i64;
            }
            let mut cost2 = 0;
            for j in 0..bwd {
                cost2 += previous_cost[((a - j - 1 + 26) % 26) as usize] as i64;
            }
            ans += cost1.min(cost2);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    shiftDistance(s: string, t: string, nextCost: number[], previousCost: number[]): number {
        let ans = 0;
        for (let i = 0; i < s.length; ++i) {
            const a = s.charCodeAt(i) - 97, b = t.charCodeAt(i) - 97;
            const fwd = (b - a + 26) % 26, bwd = (a - b + 26) % 26;
            let cost1 = 0, cost2 = 0;
            for (let j = 0, x = a; j < fwd; ++j, x = (x + 1) % 26) cost1 += nextCost[x];
            for (let j = 0, x = a; j < bwd; ++j, x = (x - 1 + 26) % 26) cost2 += previousCost[x];
            ans += Math.min(cost1, cost2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * 26), where n = length of s. For each character, we may sum up to 26 costs.
  • 🧺 Space complexity: O(1), ignoring input storage, as we use only a few variables and arrays of size 26.