Problem Description

You have two strings s and t of equal length, consisting of lowercase English letters. Your goal is to transform string s into string t by changing individual characters, with each change having an associated cost.

For each character in s, you can perform one of two operations:

• Shift forward: Move the character to the next letter in the alphabet (a→b, b→c, ..., z→a). The cost for this operation is nextCost[j], where j is the alphabet position of the current character (0 for 'a', 1 for 'b', ..., 25 for 'z').
• Shift backward: Move the character to the previous letter in the alphabet (b→a, c→b, ..., a→z). The cost for this operation is previousCost[j], where j is the alphabet position of the current character.

The alphabet wraps around, meaning 'z' shifts forward to 'a', and 'a' shifts backward to 'z'.

To transform a character from s[i] to t[i], you may need multiple shifts. For example, to change 'a' to 'c', you could either:

• Shift forward twice: 'a'→'b' (cost: nextCost[0]), then 'b'→'c' (cost: nextCost[1])
• Shift backward 24 times: 'a'→'z'→'y'→...→'c'

The shift distance is the minimum total cost required to transform all characters in s to match the corresponding characters in t.

Given strings s and t, along with arrays nextCost and previousCost (each of length 26), return the minimum total cost to transform s into t.

Intuition

For each character position, we need to find the minimum cost to transform s[i] to t[i]. Since the alphabet is circular (wraps around), we have two possible paths to reach any target character from a source character:

1. Moving forward (clockwise) through the alphabet
2. Moving backward (counter-clockwise) through the alphabet

The key insight is that we need to efficiently calculate the cost of moving from any character to any other character in both directions. Since we might need to wrap around the alphabet, a naive approach of summing costs step by step would be inefficient.

To solve this efficiently, we can use prefix sums. The idea is to precompute cumulative costs for moving forward and backward through the alphabet. However, since the alphabet wraps around, we need to handle the circular nature carefully.

The solution doubles the alphabet conceptually to handle wrap-around cases. By creating prefix sum arrays of size 2 * 26, we can represent any path between two characters without worrying about the circular boundary. For example:

• If we need to go from 'y' (position 24) to 'b' (position 1) forward, we can think of it as going to position 1 + 26 = 27 in the extended array
• This allows us to use simple subtraction of prefix sums to get the total cost

For forward movement, we build prefix sums using nextCost, repeating the pattern for two cycles. For backward movement, we build prefix sums using previousCost.

Once we have these prefix sum arrays, for each character pair (s[i], t[i]), we:

1. Calculate the forward path cost using the forward prefix sum array
2. Calculate the backward path cost using the backward prefix sum array
3. Take the minimum of these two costs

The total answer is the sum of minimum costs for all character positions.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation uses prefix sums to efficiently calculate the minimum cost of transforming each character.

Step 1: Initialize Prefix Sum Arrays

We create two prefix sum arrays s1 and s2, each of size (26 << 1 | 1) which equals 53. This size allows us to handle the circular nature of the alphabet by essentially doubling it.

m = 26
s1 = [0] * (m << 1 | 1)  # For forward costs (size 53)
s2 = [0] * (m << 1 | 1)  # For backward costs (size 53)

Step 2: Build Prefix Sums

We populate the prefix sum arrays by iterating through two full cycles of the alphabet (52 iterations):

for i in range(m << 1):  # i goes from 0 to 51
    s1[i + 1] = s1[i] + nextCost[i % m]
    s2[i + 1] = s2[i] + previousCost[(i + 1) % m]

• For s1: We accumulate nextCost[i % 26] to handle forward movement costs. The modulo operation ensures we cycle through the 26 costs twice.
• For s2: We accumulate previousCost[(i + 1) % 26] for backward movement. The (i + 1) % m indexing accounts for the fact that moving backward from position i uses the cost at position i.

Step 3: Calculate Minimum Cost for Each Character

For each character pair (a, b) from strings s and t:

for a, b in zip(s, t):
    x, y = ord(a) - ord("a"), ord(b) - ord("a")

We convert characters to their alphabet positions (0-25).

Step 4: Compute Forward and Backward Costs

c1 = s1[y + m if y < x else y] - s1[x]
c2 = s2[x + m if x < y else x] - s2[y]

• Forward cost (c1): If y < x (target comes before source in alphabet), we need to wrap around, so we use y + 26 as the endpoint. Otherwise, we use y directly. The cost is s1[endpoint] - s1[x].

• Backward cost (c2): If x < y (source comes before target), we need to wrap around backward, so we use x + 26 as the starting point. The cost is s2[starting_point] - s2[y].

Step 5: Accumulate Minimum Costs

ans += min(c1, c2)

We take the minimum of forward and backward costs for each character position and sum them up.

The algorithm runs in O(n) time where n is the length of the strings, with O(1) space for the prefix sum arrays (constant size of 53).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• s = "abc"
• t = "bcd"
• nextCost = [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]
• previousCost = [27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]

Step 1: Build Prefix Sum Arrays

We create s1 for forward costs and s2 for backward costs, each of size 53.

For s1 (forward), we accumulate nextCost values twice:

• s1[0] = 0
• s1[1] = 0 + nextCost[0] = 0 + 1 = 1
• s1[2] = 1 + nextCost[1] = 1 + 2 = 3
• s1[3] = 3 + nextCost[2] = 3 + 3 = 6
• s1[4] = 6 + nextCost[3] = 6 + 4 = 10
• ... (continuing through all 52 positions)

For s2 (backward), we accumulate previousCost values:

• s2[0] = 0
• s2[1] = 0 + previousCost[1] = 0 + 26 = 26
• s2[2] = 26 + previousCost[2] = 26 + 25 = 51
• s2[3] = 51 + previousCost[3] = 51 + 24 = 75
• s2[4] = 75 + previousCost[4] = 75 + 23 = 98
• ... (continuing through all 52 positions)

Step 2: Transform Each Character

Character 1: 'a' → 'b'

• Source position x = 0 ('a')
• Target position y = 1 ('b')
• Forward cost: Since y >= x, we use c1 = s1[1] - s1[0] = 1 - 0 = 1
• Backward cost: Since x < y, we wrap around, so c2 = s2[0 + 26] - s2[1] = s2[26] - s2[1]
  • s2[26] equals the sum of all 26 previousCost values = 351
  • c2 = 351 - 26 = 325
• Minimum cost: min(1, 325) = 1

Character 2: 'b' → 'c'

• Source position x = 1 ('b')
• Target position y = 2 ('c')
• Forward cost: Since y >= x, we use c1 = s1[2] - s1[1] = 3 - 1 = 2
• Backward cost: Since x < y, we wrap around, so c2 = s2[1 + 26] - s2[2] = s2[27] - s2[2]
  • s2[27] = s2[26] + previousCost[0] = 351 + 27 = 378
  • c2 = 378 - 51 = 327
• Minimum cost: min(2, 327) = 2

Character 3: 'c' → 'd'

• Source position x = 2 ('c')
• Target position y = 3 ('d')
• Forward cost: Since y >= x, we use c1 = s1[3] - s1[2] = 6 - 3 = 3
• Backward cost: Since x < y, we wrap around, so c2 = s2[2 + 26] - s2[3] = s2[28] - s2[3]
  • s2[28] = 378 + previousCost[1] = 378 + 26 = 404
  • c2 = 404 - 75 = 329
• Minimum cost: min(3, 329) = 3

Step 3: Calculate Total Cost Total minimum cost = 1 + 2 + 3 = 6

The algorithm efficiently finds that shifting each character forward by one position is the optimal strategy, with a total cost of 6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n) where m = 26 (the size of the alphabet) and n is the length of strings s and t.

• The first loop runs 2m iterations to build the prefix sum arrays s1 and s2, which takes O(m) time.
• The second loop iterates through each character pair in strings s and t, which takes O(n) time.
• Inside the second loop, all operations (character conversion, array lookups, and arithmetic) are O(1).
• Since m is a constant (26), the overall time complexity simplifies to O(n).

Space Complexity: O(m) where m = 26.

• Two arrays s1 and s2 are created, each of size 2m + 1 = 53, which requires O(m) space.
• All other variables (ans, x, y, c1, c2, loop counters) use constant space O(1).
• Since m is a constant (26), the space complexity is effectively O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Mapping for Backward Shifts

The Pitfall: When building the backward prefix sum array, a common mistake is using previousCost[i % m] instead of previousCost[(i + 1) % m]. This error occurs because developers often assume the indexing works the same way as forward shifts.

Why It's Wrong: When moving backward from position i, you're actually using the previousCost of the character you're moving FROM, not TO. For example:

• Moving backward from 'b' (index 1) to 'a' (index 0) uses previousCost[1] (the cost of shifting 'b' backward)
• Moving backward from 'a' (index 0) to 'z' (index 25) uses previousCost[0] (the cost of shifting 'a' backward)

Incorrect Code:

# WRONG - This uses the wrong index for backward costs
for i in range(m << 1):
    backward_prefix_sum[i + 1] = backward_prefix_sum[i] + previousCost[i % m]  # Bug!

Correct Code:

# CORRECT - Uses (i + 1) % m to get the proper cost index
for i in range(m << 1):
    backward_prefix_sum[i + 1] = backward_prefix_sum[i] + previousCost[(i + 1) % m]

2. Misunderstanding Wraparound Logic

The Pitfall: Developers might incorrectly calculate the wraparound costs by not properly adjusting the indices when the transformation requires going "around" the alphabet.

Why It's Wrong: When transforming 'z' to 'b' forward, you need to go z→a→b, which wraps around. Without adding the alphabet size to handle this wraparound in the prefix sum calculation, you'd get negative or incorrect costs.

Incorrect Approach:

# WRONG - Doesn't handle wraparound properly
forward_cost = forward_prefix_sum[target_index] - forward_prefix_sum[source_index]
backward_cost = backward_prefix_sum[source_index] - backward_prefix_sum[target_index]

Correct Approach:

# CORRECT - Adds alphabet_size when wraparound is needed
if target_index < source_index:
    forward_cost = forward_prefix_sum[target_index + alphabet_size] - forward_prefix_sum[source_index]
else:
    forward_cost = forward_prefix_sum[target_index] - forward_prefix_sum[source_index]

if source_index < target_index:
    backward_cost = backward_prefix_sum[source_index + alphabet_size] - backward_prefix_sum[target_index]
else:
    backward_cost = backward_prefix_sum[source_index] - backward_prefix_sum[target_index]

3. Off-by-One Errors in Prefix Sum Array Size

The Pitfall: Using size 26 * 2 instead of 26 * 2 + 1 for the prefix sum arrays, or using incorrect bounds in the loop.

Why It's Wrong: Prefix sum arrays need an extra element at the beginning (index 0) to represent the sum of zero elements. Without this, array access will be out of bounds or calculations will be off.

Solution: Always allocate (alphabet_size * 2 + 1) elements for the prefix sum arrays to accommodate:

• Index 0: sum of zero elements
• Indices 1-52: cumulative sums for double alphabet cycle