Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Shift Distance Between Two Strings solution and explanation

MediumArrayPrefix SumString7 min read52.8% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Shift Distance Between Two Strings
11:15
Leetcode Biweekly Contest 144 | 3361. Shift Distance Between Two Strings | CodefodCodeFod · 11:15 · 391 viewsWatch on YouTube
5 more videos on this problem
  1. Leetcode Biweekly Contest 144 | 3361. Shift Distance Between Two Strings | CodefodCodeFod · 11:15 · 391 views
  2. 3361. Shift Distance Between Two Strings (Leetcode Medium)Programming Live with Larry · 16:51 · 299 views
  3. 3361. Shift Distance Between Two Strings | Medium | Iteration | LeetCode | Module OperationLeet's Code · 11:58 · 254 views
  4. LeetCode Biweekly Contest 144 2nd question Shift Distance Between two strings LeetCode 3361R Sai Siddhu · 13:11 · 119 views
  5. Biweekly Contest 144 | First 3 Problems - 3360, 3361 & 3362 | LeetcodeAmit Choraria · 32:26 · 117 views
  6. 100441. Shift Distance Between Two Strings biweekly contest leetcode 144 c++ solutionLeetcode Solutions · 0:19 · 111 views

The problem

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:

  • 1 <= s.length == t.length <= 105
  • s and t consist only of lowercase English letters.
  • nextCost.length == previousCost.length == 26
  • 0 <= nextCost[i], previousCost[i] <= 109

Approach overview

Problem Overview: You are given two strings s and t of the same length. Each character can be shifted forward or backward in the alphabet with different costs. The goal is to compute the minimum total cost required to transform s into t character by character.

Approach 1: Greedy with Prefix Sum Cost Lookup (O(n) time, O(1) space)

Each position in the string can be solved independently. For a character s[i], you can either shift forward through the alphabet until reaching t[i], or shift backward. The key observation is that the alphabet is circular, so forward movement may wrap from 'z' to 'a', and backward movement may wrap in the opposite direction.

To compute shift costs quickly, precompute prefix sums for the forward and backward cost arrays of size 26. A prefix sum lets you calculate the total cost of shifting across a range of characters in constant time. For each index i, calculate the forward cost from s[i] to t[i] and the backward cost using the prefix arrays, then choose the minimum. Iterate through the entire string once and accumulate the result. This greedy decision works because shifts for different indices do not interact.

This approach relies heavily on efficient cumulative cost queries, which makes prefix sum preprocessing ideal. The overall scan of the strings keeps the runtime linear while memory usage remains constant because the alphabet size is fixed.

Approach 2: Dynamic Programming for Cost Optimization (O(n + 26^2) time, O(26^2) space)

A dynamic programming formulation can precompute the minimum cost to shift between every pair of letters. Treat each alphabet character as a node and transitions as shifting forward or backward with the given costs. A DP table dp[a][b] stores the minimum cost to convert character a into character b.

Build this table by simulating forward and backward movements around the alphabet while accumulating costs. Since the alphabet size is fixed (26), the preprocessing is small and predictable. Once the table is built, iterate through the strings and sum dp[s[i]][t[i]] for each position.

This approach is slightly more general and easier to reason about when modeling the alphabet as a transition graph. It still runs efficiently because the preprocessing work is bounded by the constant alphabet size. The strings themselves are processed in linear time.

Recommended for interviews: The greedy + prefix sum solution is what interviewers usually expect. It shows you recognize that each character transformation is independent and that prefix sums allow constant‑time range cost queries. Explaining the dynamic programming formulation also demonstrates strong problem modeling skills with string transformations and cost transitions over a small array domain.

Approach 1: Greedy Approach for Minimum Cost Calculation

In this approach, for each character in the string s, we compute the character's position in the alphabet (0-indexed). We do the same for string t. For each position, calculate the cost to shift from one character to the other in both clockwise and anti-clockwise directions. We select the minimum of these two costs and add it to the total cost. This provides the minimal cost needed to transform string s to string t.

def shift_distance(s, t, next_cost, prev_cost):
    cost = 0
    for i in range(len(s)):
        s_index = ord(s[i]) - ord('a')
        t_index = ord(t[i]) - ord('a')
        forward_shift = (t_index - s_index + 26) % 26
        backward_shift = (s_index - t_index + 26) % 26
        forward_cost = sum(next_cost[(s_index + j) % 26] for j in range(forward_shift))
        backward_cost = sum(prev_cost[(s_index - j + 26) % 26] for j in range(backward_shift))
        cost += min(forward_cost, backward_cost)
    return cost

s = "abab"
t = "baba"
next_cost = [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]
prev_cost = [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]
result = shift_distance(s, t, next_cost, prev_cost)
print(result)
public class ShiftDistance {
    public static int shiftDistance(String s, String t, int[] nextCost, int[] prevCost) {
        int cost = 0;
        for (int i = 0; i < s.length(); i++) {
            int s_index = s.charAt(i) - 'a';
            int t_index = t.charAt(i) - 'a';
            int forward_shift = (t_index - s_index + 26) % 26;
            int backward_shift = (s_index - t_index + 26) % 26;
            int forward_cost = 0;
            int backward_cost = 0;
            for (int j = 0; j < forward_shift; j++) {
                forward_cost += nextCost[(s_index + j) % 26];
            }
            for (int j = 0; j < backward_shift; j++) {
                backward_cost += prevCost[(s_index - j + 26) % 26];
            }
            cost += Math.min(forward_cost, backward_cost);
        }
        return cost;
    }

    public static void main(String[] args) {
        String s = "abab";
        String t = "baba";
        int[] 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};
        int[] prevCost = {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};
        int result = shiftDistance(s, t, nextCost, prevCost);
        System.out.println(result);
    }
}
#include <iostream>
#include <vector>
#include <string>

int shiftDistance(const std::string& s, const std::string& t, const std::vector<int>& nextCost, const std::vector<int>& previousCost) {
    int cost = 0;
    for (int i = 0; i < s.size(); ++i) {
        int s_index = s[i] - 'a';
        int t_index = t[i] - 'a';
        int forward_shift = (t_index - s_index + 26) % 26;
        int backward_shift = (s_index - t_index + 26) % 26;
        int forward_cost = 0;
        int backward_cost = 0;
        for (int j = 0; j < forward_shift; ++j) {
            forward_cost += nextCost[(s_index + j) % 26];
        }
        for (int j = 0; j < backward_shift; ++j) {
            backward_cost += previousCost[(s_index - j + 26) % 26];
        }
        cost += std::min(forward_cost, backward_cost);
    }
    return cost;
}

int main() {
    std::string s = "abab";
    std::string t = "baba";
    std::vector<int> 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};
    std::vector<int> 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};
    int cost = shiftDistance(s, t, nextCost, previousCost);
    std::cout << cost << std::endl;
    return 0;
}
function shiftDistance(s, t, nextCost, prevCost) {
    let cost = 0;
    for (let i = 0; i < s.length; i++) {
        const s_index = s.charCodeAt(i) - 'a'.charCodeAt(0);
        const t_index = t.charCodeAt(i) - 'a'.charCodeAt(0);
        const forward_shift = (t_index - s_index + 26) % 26;
        const backward_shift = (s_index - t_index + 26) % 26;
        let forward_cost = 0;
        let backward_cost = 0;
        for (let j = 0; j < forward_shift; j++) {
            forward_cost += nextCost[(s_index + j) % 26];
        }
        for (let j = 0; j < backward_shift; j++) {
            backward_cost += prevCost[(s_index - j + 26) % 26];
        }
        cost += Math.min(forward_cost, backward_cost);
    }
    return cost;
}

const s = "abab";
const t = "baba";
const 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];
const prevCost = [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];

console.log(shiftDistance(s, t, nextCost, prevCost));
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shiftDistance(char* s, char* t, int* nextCost, int* previousCost) {
    int cost = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        int s_index = s[i] - 'a';
        int t_index = t[i] - 'a';
        int forward_shift = (t_index - s_index + 26) % 26;
        int backward_shift = (s_index - t_index + 26) % 26;
        int forward_cost = 0;
        int backward_cost = 0;
        for (int j = 0; j < forward_shift; j++) {
            forward_cost += nextCost[(s_index + j) % 26];
        }
        for (int j = 0; j < backward_shift; j++) {
            backward_cost += previousCost[(s_index - j + 26) % 26];
        }
        cost += (forward_cost < backward_cost) ? forward_cost : backward_cost;
    }
    return cost;
}

int main() {
    char s[] = "abab";
    char t[] = "baba";
    int 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};
    int 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};
    int cost = shiftDistance(s, t, nextCost, previousCost);
    printf("%d\n", cost);
    return 0;
}
using System;

class ShiftDistanceCalculator {
    public static int ShiftDistance(string s, string t, int[] nextCost, int[] prevCost) {
        int cost = 0;
        for (int i = 0; i < s.Length; i++) {
            int s_index = s[i] - 'a';
            int t_index = t[i] - 'a';
            int forward_shift = (t_index - s_index + 26) % 26;
            int backward_shift = (s_index - t_index + 26) % 26;
            int forward_cost = 0;
            int backward_cost = 0;
            for (int j = 0; j < forward_shift; j++) {
                forward_cost += nextCost[(s_index + j) % 26];
            }
            for (int j = 0; j < backward_shift; j++) {
                backward_cost += prevCost[(s_index - j + 26) % 26];
            }
            cost += Math.Min(forward_cost, backward_cost);
        }
        return cost;
    }

    static void Main(string[] args) {
        string s = "abab";
        string t = "baba";
        int[] 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};
        int[] prevCost = {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};
        int result = ShiftDistance(s, t, nextCost, prevCost);
        Console.WriteLine(result);
    }
}

This Python solution leverages Python's built-in data handling. For each index, it calculates the minimum shift (either forward or backward) needed to transform each character, then accumulates the minimum cost across all indices to find the total shift distance.

Complexity

Time Complexity: O(n) as each character index is processed in linear time.
Space Complexity: O(1), requiring a constant amount of extra space for computation.

Try this approach in the editor

Approach 2: Dynamic Programming for Cost Optimization

To minimize costs using dynamic programming, we can track previously computed minimal costs for transformation, helping us decide more efficiently at each step. The idea is to maintain arrays that store cumulative shift costs to convert s[i] to t[i]. By leveraging previously calculated minimal operations, we avoid redundant computations, optimizing the process further for large inputs.

def dp_shift_distance(s, t, next_cost, prev_cost):
    cost = 0
    for i in range(len(s)):
        s_index = ord(s[i]) - ord('a')
        t_index = ord(t[i]) - ord('a')

        dp_forward = [0] * 26
        dp_backward = [0] * 26

        for pos in range(1, 26):
            dp_forward[pos] = dp_forward[pos - 1] + next_cost[(s_index + pos - 1) % 26]
            dp_backward[pos] = dp_backward[pos - 1] + prev_cost[(s_index - pos + 1 + 26) % 26]

        forward_needed = (t_index - s_index + 26) % 26
        backward_needed = (s_index - t_index + 26) % 26

        cost += min(dp_forward[forward_needed], dp_backward[backward_needed])

    return cost

s = "abab"
t = "baba"
next_cost = [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]
prev_cost = [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]
result = dp_shift_distance(s, t, next_cost, prev_cost)
print(result)
import java.util.Arrays;

public class DPShiftDistance {
    public static int dpShiftDistance(String s, String t, int[] nextCost, int[] prevCost) {
        int cost = 0;
        for (int i = 0; i < s.length(); i++) {
            int s_index = s.charAt(i) - 'a';
            int t_index = t.charAt(i) - 'a';

            int[] dp_forward = new int[26];
            int[] dp_backward = new int[26];
            Arrays.fill(dp_forward, 0);
            Arrays.fill(dp_backward, 0);

            for (int pos = 1; pos < 26; pos++) {
                dp_forward[pos] = dp_forward[pos - 1] + nextCost[(s_index + pos - 1) % 26];
                dp_backward[pos] = dp_backward[pos - 1] + prevCost[(s_index - pos + 1 + 26) % 26];
            }

            int forward_needed = (t_index - s_index + 26) % 26;
            int backward_needed = (s_index - t_index + 26) % 26;

            cost += Math.min(dp_forward[forward_needed], dp_backward[backward_needed]);
        }
        return cost;
    }

    public static void main(String[] args) {
        String s = "abab";
        String t = "baba";
        int[] 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};
        int[] prevCost = {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};
        int result = dpShiftDistance(s, t, nextCost, prevCost);
        System.out.println(result);
    }
}
#include <iostream>
#include <vector>
#include <algorithm>

int dpShiftDistance(const std::string& s, const std::string& t, const std::vector<int>& nextCost, const std::vector<int>& previousCost) {
    int cost = 0;
    for (int i = 0; i < s.size(); ++i) {
        int s_index = s[i] - 'a';
        int t_index = t[i] - 'a';
        std::vector<int> dp_forward(26, 0), dp_backward(26, 0);

        for (int pos = 1; pos < 26; ++pos) {
            dp_forward[pos] = dp_forward[pos - 1] + nextCost[(s_index + pos - 1) % 26];
            dp_backward[pos] = dp_backward[pos - 1] + previousCost[(s_index - pos + 1 + 26) % 26];
        }

        int forward_needed = (t_index - s_index + 26) % 26;
        int backward_needed = (s_index - t_index + 26) % 26;

        cost += std::min(dp_forward[forward_needed], dp_backward[backward_needed]);
    }
    return cost;
}

int main() {
    std::string s = "abab";
    std::string t = "baba";
    std::vector<int> 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};
    std::vector<int> 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};
    int result = dpShiftDistance(s, t, nextCost, previousCost);
    std::cout << result << std::endl;
    return 0;
}
function dpShiftDistance(s, t, nextCost, prevCost) {
    let cost = 0;
    for (let i = 0; i < s.length; i++) {
        const s_index = s.charCodeAt(i) - 'a'.charCodeAt(0);
        const t_index = t.charCodeAt(i) - 'a'.charCodeAt(0);
        const dp_forward = new Array(26).fill(0);
        const dp_backward = new Array(26).fill(0);

        for (let pos = 1; pos < 26; pos++) {
            dp_forward[pos] = dp_forward[pos - 1] + nextCost[(s_index + pos - 1) % 26];
            dp_backward[pos] = dp_backward[pos - 1] + prevCost[(s_index - pos + 1 + 26) % 26];
        }

        const forward_needed = (t_index - s_index + 26) % 26;
        const backward_needed = (s_index - t_index + 26) % 26;

        cost += Math.min(dp_forward[forward_needed], dp_backward[backward_needed]);
    }
    return cost;
}

const s = "abab";
const t = "baba";
const 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];
const prevCost = [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];

console.log(dpShiftDistance(s, t, nextCost, prevCost));
#include <stdio.h>
#include <limits.h>

int min(int a, int b) { return a < b ? a : b; }

int dpShiftDistance(char* s, char* t, int* nextCost, int* previousCost) {
    int cost = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        int s_index = s[i] - 'a';
        int t_index = t[i] - 'a';
        int dp_forward[26] = {0}, dp_backward[26] = {0};

        for (int pos = 0; pos < 26; pos++) {
            if (pos == 0) {
                dp_forward[pos] = 0;
                dp_backward[pos] = 0;
            } else {
                dp_forward[pos] = dp_forward[pos - 1] + nextCost[(s_index + pos - 1) % 26];
                dp_backward[pos] = dp_backward[pos - 1] + previousCost[(s_index - pos + 1 + 26) % 26];
            }
        }

        int forward_needed = (t_index - s_index + 26) % 26;
        int backward_needed = (s_index - t_index + 26) % 26;
        
        cost += min(dp_forward[forward_needed], dp_backward[backward_needed]);
    }
    return cost;
}

int main() {
    char s[] = "abab";
    char t[] = "baba";
    int 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};
    int 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};
    int cost = dpShiftDistance(s, t, nextCost, previousCost);
    printf("%d\n", cost);
    return 0;
}
using System;

class DPShiftDistanceCalculator {
    public static int DPShiftDistance(string s, string t, int[] nextCost, int[] prevCost) {
        int cost = 0;
        for (int i = 0; i < s.Length; i++) {
            int s_index = s[i] - 'a';
            int t_index = t[i] - 'a';
            
            int[] dp_forward = new int[26];
            int[] dp_backward = new int[26];

            for (int pos = 1; pos < 26; pos++) {
                dp_forward[pos] = dp_forward[pos - 1] + nextCost[(s_index + pos - 1) % 26];
                dp_backward[pos] = dp_backward[pos - 1] + prevCost[(s_index - pos + 1 + 26) % 26];
            }

            int forward_needed = (t_index - s_index + 26) % 26;
            int backward_needed = (s_index - t_index + 26) % 26;

            cost += Math.Min(dp_forward[forward_needed], dp_backward[backward_needed]);
        }
        return cost;
    }

    static void Main(string[] args) {
        string s = "abab";
        string t = "baba";
        int[] 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};
        int[] prevCost = {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};
        int result = DPShiftDistance(s, t, nextCost, prevCost);
        Console.WriteLine(result);
    }
}

Python’s application of dynamic programming persists in judicious employment of cost arrays, forwarding transformative efficiency on each linear character computation. Resultant cumulative minimization echoes calculations in linear time, closing each conversion step capably.

Complexity

Time Complexity: O(n * 26) in light of onerous character deliberation on 26 permutations.
Space Complexity: O(1), constrained by definite auxiliary storage adaptation.

Try this approach in the editor

Approach 3: Default Approach

function shiftDistance(s: string, t: string, nextCost: number[], previousCost: number[]): number {
    const m = 26;
    const s1: number[] = Array((m << 1) + 1).fill(0);
    const s2: number[] = Array((m << 1) + 1).fill(0);
    for (let i = 0; i < m << 1; i++) {
        s1[i + 1] = s1[i] + nextCost[i % m];
        s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
    }
    let ans = 0;
    const a = 'a'.charCodeAt(0);
    for (let i = 0; i < s.length; i++) {
        const x = s.charCodeAt(i) - a;
        const y = t.charCodeAt(i) - a;
        const c1 = s1[y + (y < x ? m : 0)] - s1[x];
        const c2 = s2[x + (x < y ? m : 0)] - s2[y];
        ans += Math.min(c1, c2);
    }
    return ans;
}
func shiftDistance(s string, t string, nextCost []int, previousCost []int) (ans int64) {
	m := 26
	s1 := make([]int64, (m<<1)+1)
	s2 := make([]int64, (m<<1)+1)
	for i := 0; i < (m << 1); i++ {
		s1[i+1] = s1[i] + int64(nextCost[i%m])
		s2[i+1] = s2[i] + int64(previousCost[(i+1)%m])
	}
	for i := 0; i < len(s); i++ {
		x := int(s[i] - 'a')
		y := int(t[i] - 'a')
		z := y
		if y < x {
			z += m
		}
		c1 := s1[z] - s1[x]
		z = x
		if x < y {
			z += m
		}
		c2 := s2[z] - s2[y]
		ans += min(c1, c2)
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Greedy Approach for Minimum Cost Calculation

Time Complexity: O(n) as each character index is processed in linear time.
Space Complexity: O(1), requiring a constant amount of extra space for computation.

Dynamic Programming for Cost Optimization

Time Complexity: O(n * 26) in light of onerous character deliberation on 26 permutations.
Space Complexity: O(1), constrained by definite auxiliary storage adaptation.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Greedy with Prefix Sum Cost LookupO(n)O(1)Best general solution when characters can be processed independently and fast cost lookup is needed
Dynamic Programming over Alphabet TransitionsO(n + 26^2)O(26^2)Useful when modeling shifts as transitions and precomputing minimum cost between all letter pairs

Frequently asked questions

Is Shift Distance Between Two Strings easy or hard?

Shift Distance Between Two Strings is typically classified as a medium difficulty problem. The main challenge is recognizing the circular alphabet behavior and using prefix sums to compute shift costs efficiently instead of simulating each step.

Shift Distance Between Two Strings Python/Java solution

Most implementations follow the same structure across languages: build prefix sums for the 26-character alphabet, compute forward and backward shift costs, and iterate through the strings accumulating the minimum cost. The logic translates directly to Python, Java, C++, C#, and JavaScript.

How to solve Shift Distance Between Two Strings in O(n)?

Precompute prefix sums for the forward and backward shift costs across the alphabet. For each index i, calculate the cost of shifting s[i] to t[i] in both directions using the prefix arrays, then add the minimum of the two. Since each position is processed once, the algorithm runs in linear time.

What is the best approach for Shift Distance Between Two Strings?

The greedy approach with prefix sums is the most efficient solution. Precompute cumulative costs for forward and backward alphabet shifts, then evaluate each character pair independently. This results in O(n) time complexity and constant space because the alphabet size is fixed.

Is Shift Distance Between Two Strings asked at Google/Amazon/Meta?

Problems involving string transformation costs and circular alphabet operations appear frequently in interviews at companies like Google and Amazon. Variants that combine prefix sums, greedy choices, and character cost transitions are common in medium-level interview rounds.

What data structure is used in Shift Distance Between Two Strings?

The solution primarily uses arrays and prefix sums. Arrays store the shift costs for moving forward or backward between characters, while prefix sums allow constant-time calculation of cumulative shift costs between two letters.

What is the time complexity of Shift Distance Between Two Strings?

The optimal solution runs in O(n) time where n is the string length. Each character pair is processed once, and prefix sums allow constant-time computation of shift costs. Space complexity remains O(1) because only fixed-size arrays of length 26 are used.

Comments

Next problem · similarShifting LettersMedium
Now write it yourselfClose this page and solve Shift Distance Between Two Strings in the editor, without looking.
Practise Shift Distance Between Two Strings