3361. Shift Distance Between Two Strings LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3361. Shift Distance Between Two Strings LeetCode Solution with the best time and space complexity. The solution to Shift Distance Between Two Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Shift Distance Between Two Strings solution in C++
Shift Distance Between Two Strings solution in Java
Shift Distance Between Two Strings solution in Python
Additional Resources

3361. Shift Distance Between Two Strings LeetCode Solution image

Problem Statement of Shift Distance Between Two Strings

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

Complexity Analysis

Time Complexity: O(26^2 + n) = O(n)
Space Complexity: O(26^2) = O(1)

3361. Shift Distance Between Two Strings LeetCode Solution in C++

class Solution {
 public:
  long long shiftDistance(string s, string t, vector<int>& nextCost,
                          vector<int>& previousCost) {
    long ans = 0;
    // prev[i][j] := the prev cost to shift from ('a' + i) to ('a' + j)
    vector<vector<long>> prev(26, vector<long>(26));
    // next[i][j] := the next cost to shift from ('a' + i) to ('a' + j)
    vector<vector<long>> next(26, vector<long>(26));

    for (int i = 0; i < 26; ++i) {
      long cost = 0;
      for (int j = 0; j < 26; ++j) {
        next[i][(i + j) % 26] = cost;
        cost += nextCost[(i + j) % 26];
      }
    }

    for (int i = 0; i < 26; ++i) {
      long cost = 0;
      for (int j = 0; j < 26; ++j) {
        prev[i][(i - j + 26) % 26] = cost;
        cost += previousCost[(i - j + 26) % 26];
      }
    }

    for (int i = 0; i < s.length(); ++i) {
      const int a = s[i] - 'a';
      const int b = t[i] - 'a';
      ans += min(next[a][b], prev[a][b]);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3361. Shift Distance Between Two Strings LeetCode Solution in Java

class Solution {
  public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
    long ans = 0;
    // prev[i][j]: the prev cost to shift from ('a' + i) to ('a' + j)
    long[][] prev = new long[26][26];
    // next[i][j]: the next cost to shift from ('a' + i) to ('a' + j)
    long[][] next = new long[26][26];

    for (int i = 0; i < 26; ++i) {
      long cost = 0;
      for (int j = 0; j < 26; ++j) {
        next[i][(i + j) % 26] = cost;
        cost += nextCost[(i + j) % 26];
      }
    }

    for (int i = 0; i < 26; ++i) {
      long cost = 0;
      for (int j = 0; j < 26; ++j) {
        prev[i][(i - j + 26) % 26] = cost;
        cost += previousCost[(i - j + 26) % 26];
      }
    }

    for (int i = 0; i < s.length(); ++i) {
      final int a = s.charAt(i) - 'a';
      final int b = t.charAt(i) - 'a';
      ans += Math.min(next[a][b], prev[a][b]);
    }

    return ans;
  }
}
// code provided by PROGIEZ

3361. Shift Distance Between Two Strings LeetCode Solution in Python

class Solution:
  def shiftDistance(
      self,
      s: str,
      t: str,
      nextCost: list[int],
      previousCost: list[int]
  ) -> int:
    ans = 0
    # prev[i][j]: the prev cost to shift from ('a' + i) to ('a' + j)
    prev = [[0] * 26 for _ in range(26)]
    # next[i][j]: the next cost to shift from ('a' + i) to ('a' + j)
    next = [[0] * 26 for _ in range(26)]

    for i in range(26):
      cost = 0
      for j in range(26):
        next[i][(i + j) % 26] = cost
        cost += nextCost[(i + j) % 26]

    for i in range(26):
      cost = 0
      for j in range(26):
        prev[i][(i - j + 26) % 26] = cost
        cost += previousCost[(i - j + 26) % 26]

    for a, b in zip(s, t):
      i = ord(a) - ord('a')
      j = ord(b) - ord('a')
      ans += min(next[i][j], prev[i][j])

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents