Shift Distance Between Two Strings

Shift Distance Between Two Strings

What is this problem about?

The Shift Distance Between Two Strings interview question gives you two strings s and t of equal length, and an array nextCost and previousCost of size 26 representing the cost to shift a character one step forward or backward in the alphabet. Find the minimum total cost to transform s into t by independently shifting each character of s to its corresponding character in t, choosing between shifting forward or backward for each position.

Why is this asked in interviews?

Google asks this problem because it tests prefix sum optimization on per-character cost accumulation. The naive approach sums costs for each individual shift, but using prefix sums precomputed over nextCost and previousCost allows computing the cost of shifting from character a to character b by any number of steps in O(1) — turning an O(26) per-character cost into O(1) with O(26) preprocessing.

Algorithmic pattern used

The pattern is prefix sum precomputation on circular alphabet. Precompute two prefix sum arrays: next_prefix[i] = cost of shifting forward from 'a' to the character at index i, and prev_prefix[i] = cost of shifting backward from 'z' to the character at index i. For each character pair (s[i], t[i]), compute: forward cost = shift from s[i] to t[i] going forward (wrapping around alphabet). Backward cost = shift going backward. Take the minimum of the two for each position. Sum all minimums.

Example explanation

s = "ab", t = "ba". nextCost = [all 1s], previousCost = [all 1s].

Position 0: 'a' → 'b'. Forward: 1 step × 1 cost = 1. Backward: 25 steps × 1 cost = 25. Min = 1. Position 1: 'b' → 'a'. Forward: 25 steps × 1 cost = 25. Backward: 1 step × 1 cost = 1. Min = 1.

Total: 2.

With prefix sums: forward_cost('a', 'b') = next_prefix['b'] - next_prefix['a']. For wrap-around, use modular arithmetic.

Common mistakes candidates make

• Not handling the circular wrap-around when the forward shift goes 'z' → 'a' — total alphabet size is 26, so wrap-around cost = total_next_cost - prefix_up_to_source + prefix_up_to_dest.
• Computing costs character by character without prefix sums — O(26) per character is O(26n) total; prefix sums give O(26 + n).
• Not considering both directions for each character pair — for each (s[i], t[i]), always compute both forward and backward costs.
• Using the wrong index convention — ensure prefix sums are aligned with 0-indexed characters (a=0, b=1, ..., z=25).

Interview preparation tip

For the Shift Distance Between Two Strings coding problem, the prefix sum string array interview pattern is the optimization. The key insight: cost of shifting from character i to character j forward is sum(nextCost[i..j-1]) — a range sum computable in O(1) with prefix sums. Google interviewers value this optimization over the naive loop. Practice building circular prefix sums — they appear in problems involving clockwise/counterclockwise costs on circular structures like rotary dials, ring buffers, and modular distance computations.