Shift Distance Between Two Strings - Practice Coding Problems

Shift Distance Between Two Strings - 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.

Input & Output

Example 1 — Basic Transformation

$ Input: s = "abc", t = "bcd", nextCost = [1,1,1,1,...], previousCost = [1,1,1,1,...]

› Output: 3

💡 Note: Transform 'a'→'b' (cost 1), 'b'→'c' (cost 1), 'c'→'d' (cost 1). Total cost = 3

Example 2 — Wraparound Case

$ Input: s = "za", t = "ab", nextCost = [1,1,1,...], previousCost = [2,2,2,...]

› Output: 3

💡 Note: Transform 'z'→'a' (cost 1 forward), 'a'→'b' (cost 1 forward). Total cost = 2

Example 3 — Choose Backward Path

$ Input: s = "ab", t = "ba", nextCost = [10,10,...], previousCost = [1,1,...]

› Output: 2

💡 Note: For 'a'→'b': backward path cheaper. For 'b'→'a': backward path cheaper. Total cost using backward = 2

Constraints

1 ≤ s.length == t.length ≤ 10⁵
s and t consist only of lowercase English letters
nextCost.length == previousCost.length == 26
1 ≤ nextCost[i], previousCost[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Source string s and target string t with cost arrays

Character Transformation

For each position, find cheaper path (forward vs backward)

Minimum Total Cost

Sum of all optimal character transformation costs

Key Takeaway

🎯 Key Insight: The alphabet forms a circle - sometimes going backward or wrapping around is cheaper than the direct forward path

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is that the alphabet is circular, so we can go forward or backward to transform each character. The optimal approach uses prefix sums to calculate range costs in O(1) time. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Direct Path Calculation	O(n × 26)	O(1)	Calculate both forward and backward costs directly for each character transformation
Prefix Sum Optimization	O(n)	O(1)	Use prefix sums to calculate path costs in O(1) time for any character transformation

Direct Path Calculation — Algorithm Steps

For each character position, find the alphabet indices
Calculate forward path cost by summing nextCost values
Calculate backward path cost by summing previousCost values
Choose minimum cost for each character and sum total

Visualization

Tap to expand

Step-by-Step Walkthrough

Character Mismatch

Find characters that need transformation

Calculate Both Paths

Sum costs going forward and backward

Choose Minimum

Pick the cheaper path for each character

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(char* s, char* t, int* nextCost, int* previousCost) {
    long long totalCost = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        if (s[i] == t[i]) continue;
        
        int start = s[i] - 'a';
        int end = t[i] - 'a';
        
        // Calculate forward cost
        long long forwardCost = 0;
        int curr = start;
        while (curr != end) {
            forwardCost += nextCost[curr];
            curr = (curr + 1) % 26;
        }
        
        // Calculate backward cost
        long long backwardCost = 0;
        curr = start;
        while (curr != end) {
            curr = (curr - 1 + 26) % 26;
            backwardCost += previousCost[curr];
        }
        
        totalCost += (forwardCost < backwardCost) ? forwardCost : backwardCost;
    }
    
    return totalCost;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    fgets(t, sizeof(t), stdin);
    t[strcspn(t, "\n")] = 0;
    
    int nextCost[26], previousCost[26];
    
    // Parse nextCost array
    char line[1000];
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    for (int i = 0; i < 26; i++) {
        nextCost[i] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse previousCost array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    for (int i = 0; i < 26; i++) {
        previousCost[i] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(s, t, nextCost, previousCost));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 26)

For each of n characters, we may traverse up to 26 alphabet positions

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculations, no extra data structures

✓ Linear Space

34.6K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Path Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler