We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shift Distance Between Two Strings

Number: 3591

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two strings s and t of equal length along with two integer arrays nextCost and previousCost (each of length 26), determine the minimum total cost to transform s into t by performing operations on each character. In one operation you can choose any index and either shift that character to its next letter (wrapping around from 'z' to 'a') at a cost determined by nextCost for the current character, or shift it to its previous letter (wrapping from 'a' to 'z') at a cost determined by previousCost for the current character. The cost for each operation depends on the letter before shifting. The goal is to compute the sum of minimum costs required over all characters to turn s into t.

Key Insights

  • The transformation for each character is independent.
  • For each character transformation from s[i] to t[i], there are two possible directions:
    • Forward (using next operations): The number of shifts is (target - source + 26) mod 26.
    • Backward (using previous operations): The number of shifts is (source - target + 26) mod 26.
  • For each shift the cost is determined by the current character's cost using the appropriate cost array (nextCost or previousCost). Thus, the total cost for a given direction is the sum of costs for each intermediate character in that directional sequence.
  • The answer is the sum over all indices where for each index, we choose the minimal cost between shifting forward or backward.

Space and Time Complexity

Time Complexity: O(n * 26) where n is the length of the string (each character’s transformation takes at most 26 steps). Space Complexity: O(1) extra space (besides input storage) since the work is done in constant extra space.

Solution

For each character in s (with index i), determine the number of shifts required in the forward direction by computing (t[i] - s[i] + 26) mod 26. Then compute the total cost by simulating the forward shifts; for each shift the cost is nextCost[current_position]. Similarly, compute the backward shifts needed using (s[i] - t[i] + 26) mod 26 and sum the corresponding previousCost values. Finally, add the minimum of the two computed costs to a running total.

A key detail is that while the number of shifts is fixed by the difference in positions, the cost for each shift depends on the letter that is being shifted. Given the small fixed maximum of 26 shifts per character transformation, a simple loop is efficient enough. This simulation approach avoids any pitfalls of trying to “mix” directions—since the optimal move is always to move continuously in one direction.

Code Solutions

# Python solution with line-by-line comments
def shiftDistance(s, t, nextCost, previousCost):
    total_cost = 0
    for c_from, c_to in zip(s, t):
        # Find numeric positions in the alphabet (0-indexed)
        start = ord(c_from) - ord('a')
        end = ord(c_to) - ord('a')
        
        # Calculate forward steps required (wrap-around using modulo)
        forward_steps = (end - start + 26) % 26
        cost_forward = 0
        current = start
        # Accumulate cost for moving forward using nextCost
        for _ in range(forward_steps):
            cost_forward += nextCost[current]  # cost based on the current letter
            current = (current + 1) % 26         # move to the next letter, wrap if needed
        
        # Calculate backward steps required
        backward_steps = (start - end + 26) % 26
        cost_backward = 0
        current = start
        # Accumulate cost for moving backward using previousCost
        for _ in range(backward_steps):
            cost_backward += previousCost[current]  # cost based on the current letter
            current = (current - 1 + 26) % 26         # move to previous letter, wrap if needed
        
        # Choose the minimum of the two directional costs for this character
        total_cost += min(cost_forward, cost_backward)
    return total_cost

# Example usage:
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]
print(shiftDistance(s, t, nextCost, previousCost))  # Output: 2
← Back to All Questions