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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shift Distance Between Two Strings

Difficulty: Medium

Problem Description

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 of the following actions:

  • Shift s[i] to the next letter in the alphabet, costing nextCost[j] where j is the index of s[i] in the alphabet.
  • Shift s[i] to the previous letter in the alphabet, costing 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.

Key Insights

  • The operations are circular, meaning 'a' can become 'z' and 'z' can become 'a'.
  • Each character transformation has a defined cost based on its position in the alphabet.
  • The problem can be approached using a greedy algorithm, calculating the cost for each character in the strings s and t.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the strings s and t, as we need to iterate through each character once.
Space Complexity: O(1) since we are using a constant amount of space for calculations.

Solution

To solve the problem, we will:

  1. Iterate over each character of the strings s and t.
  2. For each character, calculate the cost to shift from s[i] to t[i] using both possible operations (next and previous).
  3. Accumulate the minimum cost for each character transformation to get the total shift distance.

We will use basic arithmetic to determine the costs based on the character's position in the alphabet.

Code Solutions

def shiftDistance(s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int:
    total_cost = 0
    for i in range(len(s)):
        # Calculate positions in the alphabet (0-25)
        pos_s = ord(s[i]) - ord('a')
        pos_t = ord(t[i]) - ord('a')
        
        # Calculate cost to shift forward and backward
        forward_steps = (pos_t - pos_s) % 26
        backward_steps = (pos_s - pos_t) % 26
        
        cost_forward = forward_steps * nextCost[pos_s]
        cost_backward = backward_steps * previousCost[pos_s]
        
        # Add the minimum cost to total cost
        total_cost += min(cost_forward, cost_backward)
    
    return total_cost
← Back to All Questions