Shift distance between two strings

Array String Prefix Sum

53.5% acceptance

Feb 24, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shift_distance(s: String, t: String, next_cost: Vec<i32>, previous_cost: Vec<i32>) -> i64 {
    // Precompute prefix sums for forward (next) and backward (previous) directions
    // For going forward from j by d steps: sum next_cost[j], next_cost[(j+1)%26], ...
    // Use prefix sum on doubled array for circular
    let nc: Vec<i64> = next_cost.iter().map(|&x| x as i64).collect();
    let pc: Vec<i64> = previous_cost.iter().map(|&x| x as i64).collect();

    // prefix_next[i] = sum of next_cost[0..i]
    let mut prefix_next = vec![0i64; 27];
    for i in 0..26 { prefix_next[i+1] = prefix_next[i] + nc[i]; }

    // For going forward from a to b: cost = sum of next_cost[a..b] (circular)
    let forward_cost = |a: usize, b: usize| -> i64 {
      if a <= b {
        prefix_next[b] - prefix_next[a]
      } else {
        // a > b: wrap around: a..26 + 0..b
        prefix_next[26] - prefix_next[a] + prefix_next[b]
      }
    };

    // For going backward from a to b: cost = sum of previous_cost going backward
    // Going backward from a by 1 step: costs previous_cost[a]
    // Going backward from a to b (b < a): previous_cost[a] + previous_cost[a-1] + ... + previous_cost[b+1]
    let mut prefix_prev = vec![0i64; 27];
    for i in 0..26 { prefix_prev[i+1] = prefix_prev[i] + pc[i]; }

    let backward_cost = |a: usize, b: usize| -> i64 {
      // going backward from a to b (i.e., we step a -> a-1 -> ... -> b)
      // cost = sum previous_cost[a] + ... + previous_cost[b+1]
      // But going backward wraps around: if b > a, we go a -> a-1 -> ... -> 0 -> 25 -> ... -> b
      if a >= b {
        // non-wrapping: sum previous_cost[b+1..=a]
        prefix_prev[a+1] - prefix_prev[b+1]
      } else {
        // wrapping: a -> 0 (cost: prefix_prev[a+1] - prefix_prev[0+1] = prefix_prev[a+1] - pc[0])
        // actually: a -> 0 costs previous_cost[a] + previous_cost[a-1] + ... + previous_cost[0]
        //           wait no: previous step from index j costs previous_cost[j]
        // From a backward: step to a-1 (costs previous_cost[a]), then a-1, ..., 0 (costs previous_cost[0])
        //   then 25 (costs previous_cost[25]), ..., b+1 (costs previous_cost[b+1])
        // Hmm, need to reconsider. previous_cost[j] = cost to shift j -> j-1 (with wrap)
        // Going a -> a-1: costs previous_cost[a]
        // Going 0 -> 25: costs previous_cost[0]
        // So backward from a wrapping to b: previous_cost[a] + ... + previous_cost[0] + previous_cost[25] + ... + previous_cost[b+1]
        // = prefix_prev[a+1] (from 0..=a) + (prefix_prev[26] - prefix_prev[b+1]) (from b+1..=25)
        prefix_prev[a+1] + (prefix_prev[26] - prefix_prev[b+1])
      }
    };

    let sb: Vec<usize> = s.bytes().map(|b| (b - b'a') as usize).collect();
    let tb: Vec<usize> = t.bytes().map(|b| (b - b'a') as usize).collect();

    let mut total = 0i64;
    for i in 0..sb.len() {
      let a = sb[i];
      let b = tb[i];
      if a == b { continue; }
      let fwd = forward_cost(a, b);
      let bwd = backward_cost(a, b);
      total += fwd.min(bwd);
    }
    total
  }
}