LeetCode 3361 - Shift Distance Between Two Strings

LeetCode Problem 3361

Difficulty: 🟡 Medium
Topics: Array, String, Prefix Sum

Solution

Problem Understanding

The problem gives us two strings, s and t, of equal length. We want to transform s into t character by character using cyclic alphabet shifts.

For every character in s, we are allowed to repeatedly perform one of two operations:

1. Shift the character forward to the next letter in the alphabet.
2. Shift the character backward to the previous letter in the alphabet.

The alphabet is circular. That means:

• Shifting 'z' forward becomes 'a'
• Shifting 'a' backward becomes 'z'

Each individual shift operation has a cost, and the cost depends on the current character before the shift happens.

If we shift a character forward from alphabet index j, the cost is nextCost[j].

If we shift a character backward from alphabet index j, the cost is previousCost[j].

The goal is to compute the minimum total cost needed to convert the entire string s into t.

The important detail is that every position is independent. The operation performed on one character does not affect any other character. Therefore, the total answer is simply the sum of the minimum conversion cost for each corresponding character pair.

The constraints are large:

• s.length can be up to 10^5
• Costs can be as large as 10^9

This immediately tells us that any expensive per-character simulation will likely be too slow. Since there are only 26 lowercase letters, we should take advantage of the small alphabet size.

There are several edge cases worth identifying early:

• The cheapest path may involve wrapping around the alphabet.
• Moving forward is not always cheaper than moving backward.
• Costs may be zero.
• The shortest number of shifts is not necessarily the minimum-cost path.
• Characters may already match, producing zero cost.
• Costs can become very large, so the final answer must use 64-bit integers.

Approaches

Brute Force Approach

A straightforward solution is to process every character independently and simulate both possible directions:

• Move forward from s[i] until reaching t[i]
• Move backward from s[i] until reaching t[i]

For each direction, we repeatedly:

• Add the corresponding operation cost
• Move to the next or previous character

Then we take the smaller of the two costs.

Since the alphabet contains only 26 characters, each simulation takes at most 26 operations. For every position in the string, we perform two simulations.

This works correctly because every possible cyclic path is explored in both directions.

However, this solution still performs repeated traversal work for every character pair. While 26 * n is technically acceptable, we can do better conceptually by preprocessing cumulative costs and turning each query into constant-time range computations.

Key Insight

The alphabet size is fixed at 26, which is extremely small.

Instead of repeatedly simulating shifts for every character pair, we can precompute prefix sums for forward and backward movement costs.

The important observation is:

• Forward movement always follows one deterministic cyclic path.
• Backward movement also follows one deterministic cyclic path.

Therefore, the minimum cost between two characters is simply:

min(forward_cost, backward_cost)

We can efficiently compute these costs using cyclic prefix sums.

To simplify wraparound handling, we duplicate the alphabet costs to length 52. This allows every cyclic traversal to become a normal contiguous range sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26 × n)	O(1)	Simulates shifts for every character pair
Optimal	O(n + 26)	O(26)	Uses prefix sums for constant-time cost queries

Algorithm Walkthrough

Step 1: Build Forward Prefix Sums

We create an array representing forward movement costs across two copies of the alphabet.

For each index i:

• Moving from character i % 26
• To (i + 1) % 26
• Costs nextCost[i % 26]

We build a prefix sum array so we can quickly compute the total forward movement cost between any two positions.

Step 2: Build Backward Prefix Sums

Similarly, we build another prefix sum array for backward movement.

For each index i:

• Moving backward from character i % 26
• Costs previousCost[i % 26]

Again, duplicating the alphabet allows wraparound ranges to become contiguous intervals.

Step 3: Process Each Character Pair

For every position i:

• Convert s[i] and t[i] into alphabet indices.
• Compute the forward movement cost.
• Compute the backward movement cost.
• Add the smaller value to the answer.

Step 4: Compute Forward Cost

Suppose:

start = index of s[i]
end = index of t[i]

If end < start, we add 26 to end to account for wraparound.

Then:

forward_cost =
prefix_forward[end] - prefix_forward[start]

This represents all forward transitions needed to reach the target.

Step 5: Compute Backward Cost

For backward movement:

• If start < end, add 26 to start

Then:

backward_cost =
prefix_backward[start + 1] - prefix_backward[end + 1]

This computes the total cost of stepping backward cyclically.

Step 6: Return the Total

Accumulate the minimum cost for every position and return the final answer.

Why it works

For any pair of characters, there are only two possible cyclic traversal directions:

• Forward
• Backward

Each direction follows a fixed deterministic path around the alphabet. The prefix sums allow us to compute the exact total cost of that path in constant time.

Since the optimal transformation for each position is independent of every other position, summing the minimum per-position costs produces the globally optimal answer.

Python Solution

from typing import List

class Solution:
    def shiftDistance(
        self,
        s: str,
        t: str,
        nextCost: List[int],
        previousCost: List[int]
    ) -> int:

        # Prefix sums for forward movement
        forward_prefix = [0] * 53

        for i in range(52):
            forward_prefix[i + 1] = (
                forward_prefix[i] +
                nextCost[i % 26]
            )

        # Prefix sums for backward movement
        backward_prefix = [0] * 53

        for i in range(52):
            backward_prefix[i + 1] = (
                backward_prefix[i] +
                previousCost[i % 26]
            )

        total_cost = 0

        for source_char, target_char in zip(s, t):

            start = ord(source_char) - ord('a')
            end = ord(target_char) - ord('a')

            # Forward direction
            forward_end = end
            if forward_end < start:
                forward_end += 26

            forward_cost = (
                forward_prefix[forward_end] -
                forward_prefix[start]
            )

            # Backward direction
            backward_start = start
            if backward_start < end:
                backward_start += 26

            backward_cost = (
                backward_prefix[backward_start + 1] -
                backward_prefix[end + 1]
            )

            total_cost += min(forward_cost, backward_cost)

        return total_cost

The implementation begins by building two prefix sum arrays.

forward_prefix stores cumulative forward-shift costs across two copies of the alphabet. Duplicating the alphabet avoids special-case wraparound logic.

backward_prefix does the same for backward shifts.

For each character pair:

• We convert letters into indices from 0 to 25.
• We compute the forward traversal cost using a prefix sum range.
• We compute the backward traversal cost similarly.
• We add the smaller cost to the running total.

The algorithm never explicitly simulates shifts. Every character pair is processed in constant time.

Go Solution

func shiftDistance(s string, t string, nextCost []int, previousCost []int) int64 {

	forwardPrefix := make([]int64, 53)

	for i := 0; i < 52; i++ {
		forwardPrefix[i+1] =
			forwardPrefix[i] + int64(nextCost[i%26])
	}

	backwardPrefix := make([]int64, 53)

	for i := 0; i < 52; i++ {
		backwardPrefix[i+1] =
			backwardPrefix[i] + int64(previousCost[i%26])
	}

	var totalCost int64 = 0

	for i := 0; i < len(s); i++ {

		start := int(s[i] - 'a')
		end := int(t[i] - 'a')

		// Forward direction
		forwardEnd := end

		if forwardEnd < start {
			forwardEnd += 26
		}

		forwardCost :=
			forwardPrefix[forwardEnd] -
				forwardPrefix[start]

		// Backward direction
		backwardStart := start

		if backwardStart < end {
			backwardStart += 26
		}

		backwardCost :=
			backwardPrefix[backwardStart+1] -
				backwardPrefix[end+1]

		if forwardCost < backwardCost {
			totalCost += forwardCost
		} else {
			totalCost += backwardCost
		}
	}

	return totalCost
}

The Go implementation closely mirrors the Python solution.

The most important Go-specific detail is integer overflow handling. Since costs can reach 10^9 and the string length can reach 10^5, the total result can exceed 32-bit integer range. Therefore, all prefix sums and the final answer use int64.

Slices are used for the prefix arrays, and string indexing is safe because the input only contains lowercase ASCII letters.

Worked Examples

Example 1

s = "abab"
t = "baba"

Cost Arrays

nextCost[0] = 100
previousCost[0] = 1
previousCost[1] = 100
All others are 0

Character-by-Character Processing

Position	From	To	Forward Cost	Backward Cost	Chosen
0	a	b	100	1	1
1	b	a	0	100	0
2	a	b	100	1	1
3	b	a	0	100	0

Total:

1 + 0 + 1 + 0 = 2

Final answer:

2

Example 2

s = "leet"
t = "code"

All movement costs equal 1.

Character-by-Character Processing

Position	From	To	Forward Steps	Backward Steps	Minimum
0	l	c	17	9	9
1	e	o	10	16	10
2	e	d	25	1	1
3	t	e	11	15	11

Total:

9 + 10 + 1 + 11 = 31

Final answer:

31

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + 26)	Prefix sums are built once, each character pair is processed in O(1)
Space	O(26)	Prefix arrays have constant size

The preprocessing work is constant because the alphabet size never changes. After preprocessing, every character conversion becomes a constant-time calculation using prefix sum ranges. Therefore, the overall complexity scales linearly with the input string length.

Test Cases

from typing import List

class Solution:
    def shiftDistance(
        self,
        s: str,
        t: str,
        nextCost: List[int],
        previousCost: List[int]
    ) -> int:

        forward_prefix = [0] * 53

        for i in range(52):
            forward_prefix[i + 1] = (
                forward_prefix[i] +
                nextCost[i % 26]
            )

        backward_prefix = [0] * 53

        for i in range(52):
            backward_prefix[i + 1] = (
                backward_prefix[i] +
                previousCost[i % 26]
            )

        total_cost = 0

        for source_char, target_char in zip(s, t):

            start = ord(source_char) - ord('a')
            end = ord(target_char) - ord('a')

            forward_end = end
            if forward_end < start:
                forward_end += 26

            forward_cost = (
                forward_prefix[forward_end] -
                forward_prefix[start]
            )

            backward_start = start
            if backward_start < end:
                backward_start += 26

            backward_cost = (
                backward_prefix[backward_start + 1] -
                backward_prefix[end + 1]
            )

            total_cost += min(forward_cost, backward_cost)

        return total_cost

sol = Solution()

# Example 1
assert sol.shiftDistance(
    "abab",
    "baba",
    [100] + [0] * 25,
    [1, 100] + [0] * 24
) == 2  # chooses wraparound directions

# Example 2
assert sol.shiftDistance(
    "leet",
    "code",
    [1] * 26,
    [1] * 26
) == 31  # uniform costs

# Already equal strings
assert sol.shiftDistance(
    "abc",
    "abc",
    [5] * 26,
    [5] * 26
) == 0  # no operations needed

# Single-character wraparound forward
assert sol.shiftDistance(
    "z",
    "a",
    [3] * 26,
    [10] * 26
) == 3  # direct forward wrap

# Single-character wraparound backward
assert sol.shiftDistance(
    "a",
    "z",
    [10] * 26,
    [2] * 26
) == 2  # direct backward wrap

# Zero-cost transitions
assert sol.shiftDistance(
    "abc",
    "def",
    [0] * 26,
    [0] * 26
) == 0  # all operations free

# Prefer longer but cheaper route
next_cost = [100] * 26
previous_cost = [1] * 26

assert sol.shiftDistance(
    "a",
    "b",
    next_cost,
    previous_cost
) == 25  # cheaper to go backward 25 times

# Large values
assert sol.shiftDistance(
    "a",
    "b",
    [10**9] * 26,
    [10**9] * 26
) == 10**9  # verifies large integer handling

# Multiple mixed transitions
assert sol.shiftDistance(
    "azby",
    "byaz",
    [1] * 26,
    [2] * 26
) == 8  # mixed forward and backward choices

Test Summary

Test	Why
Example 1	Verifies asymmetric costs and wraparound
Example 2	Verifies uniform-cost behavior
Equal strings	Ensures zero-cost handling
z -> a	Tests forward wraparound
a -> z	Tests backward wraparound
Zero-cost arrays	Ensures free transitions work
Longer but cheaper path	Confirms minimum-cost logic instead of minimum-steps logic
Large costs	Verifies 64-bit arithmetic
Mixed transitions	Tests multiple independent decisions

Edge Cases

One important edge case occurs when the source and target characters are already equal. A buggy implementation might still attempt cyclic traversal and accidentally add unnecessary costs. In this solution, both forward and backward ranges become empty intervals, producing zero cost naturally.

Another important case is wraparound movement. For example, converting 'z' to 'a' or 'a' to 'z'. Without careful cyclic handling, range computations can become incorrect or negative. Duplicating the alphabet to length 52 eliminates special wraparound cases and guarantees all traversals become contiguous ranges.

A particularly tricky case is when the cheapest path is not the one using fewer shifts. For example, moving backward 25 times may cost less than moving forward once. A naive shortest-path interpretation would fail here. This implementation explicitly computes both total directional costs and selects the minimum, guaranteeing correctness even with highly uneven cost distributions.

Another subtle issue is integer overflow. Costs can reach 10^9, and there can be 10^5 characters. The total may therefore exceed 32-bit integer range. The Go solution uses int64, and Python integers automatically handle arbitrary precision.