Skip to main content
Talentd

Shift Distance Between Two Strings - Solution & Explanation

MediumArrayStringPrefix Sum21 min readAsked at: Google
Practice this problem

Problem Statement

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.

In this C solution, we iterate over each character of the strings s and t. We calculate both the forward shift and the backward shift to check which transformation is cheaper. The minimum cost for each index is accumulated into cost, which we return as the shift distance.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of string s. Each character transformation is analyzed in constant time.
Space Complexity: O(1), since no additional data structures are used apart from variable storage.

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.

This C solution uses a dynamic programming approach by setting up two arrays to keep track of the minimal forward and backward shift costs for each position in a circular manner around the alphabet. By iterating through and updating these dynamic arrays for each index of s, we efficiently determine the minimal cost paths to form t.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 26) due to computing costs for each possible position of the alphabet per character in s.
Space Complexity: O(26) = O(1), given fixed-length auxiliary arrays.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach for Minimum Cost Calculation

Time Complexity: O(n), where n is the length of string s. Each character transformation is analyzed in constant time.
Space Complexity: O(1), since no additional data structures are used apart from variable storage.

Dynamic Programming for Cost Optimization

Time Complexity: O(n * 26) due to computing costs for each possible position of the alphabet per character in s.
Space Complexity: O(26) = O(1), given fixed-length auxiliary arrays.

Default Approach—

Detailed 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

Video Solution

Leetcode Biweekly Contest 144 | 3361. Shift Distance Between Two Strings | Codefod • CodeFod • 391 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Shift Distance Between Two Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shifting Letters

Next

Shifting Letters II