Leetcode problem: 3361. Shift Distance Between Two Strings

Description:

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:

0 <= nextCost[i], previousCost[i] <= 10⁹

1 <= s.length == t.length <= 10⁵

s and t consist only of lowercase English letters.

nextCost.length == previousCost.length == 26

Solution:

class Solution {
    public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        int len = s.length();
        long totalCost = 0;

        for (int i = 0; i < len; i++) {
            int start = s.charAt(i) - 'a';
            int end = t.charAt(i) - 'a';

            if (start == end) continue;

            long forwardCost = 0, backwardCost = 0;

            // Calculate forward (next) cost
            int j = start;
            while (j != end) {
                forwardCost += nextCost[j];
                j = (j + 1) % 26;
            }

            // Calculate backward (previous) cost
            j = start;
            while (j != end) {
                j = (j - 1 + 26) % 26;
                backwardCost += previousCost[(j + 1) % 26];
            }

            // Add the minimum of forward and backward cost
            totalCost += Math.min(forwardCost, backwardCost);
        }

        return totalCost;
    }
}
Approach:
This method calculates the minimum total cost to convert string s into string t, character by character, using circular shifts in the English alphabet.

🧠 Core Idea:
Each character in s can be shifted to the corresponding character in t by:

Moving forward (i.e., from 'a' to 'z' in circular order using nextCost)

Moving backward (i.e., from 'z' to 'a' in reverse using previousCost)

The method chooses the cheapest path (forward or backward) for each character transformation.

⚙️ How It Works:
Loop through each character in both strings s and t.

Convert each character to its index (0 for 'a', 25 for 'z') using char - 'a'.

If the characters are already equal, skip to the next character.

If not:

Calculate forward cost:

Move from the current character index to the target, wrapping around if needed.

Use values from nextCost[] for each shift.

Calculate backward cost:

Move from the current character index to the target in reverse.

Use values from previousCost[] for each shift.

Add the minimum of the two costs to the totalCost.

Return totalCost after processing all characters.

📌 Edge Cases Handled:
Circular shifts from 'z' to 'a' or 'a' to 'z' are properly handled using modulo arithmetic.

No cost is added if the characters are already equal.

Related posts: