2976. Minimum Cost to Convert String I LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2976. Minimum Cost to Convert String I LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Convert String I 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
Minimum Cost to Convert String I solution in C++
Minimum Cost to Convert String I solution in Java
Minimum Cost to Convert String I solution in Python
Additional Resources

2976. Minimum Cost to Convert String I LeetCode Solution image

Problem Statement of Minimum Cost to Convert String I

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].
You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.
Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.
Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = “abcd”, target = “acbe”, original = [“a”,”b”,”c”,”c”,”e”,”d”], changed = [“b”,”c”,”b”,”e”,”b”,”e”], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string “abcd” to string “acbe”:
– Change value at index 1 from ‘b’ to ‘c’ at a cost of 5.
– Change value at index 2 from ‘c’ to ‘e’ at a cost of 1.
– Change value at index 2 from ‘e’ to ‘b’ at a cost of 2.
– Change value at index 3 from ‘d’ to ‘e’ at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = “aaaa”, target = “bbbb”, original = [“a”,”c”], changed = [“c”,”b”], cost = [1,2]
Output: 12
Explanation: To change the character ‘a’ to ‘b’ change the character ‘a’ to ‘c’ at a cost of 1, followed by changing the character ‘c’ to ‘b’ at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of ‘a’ to ‘b’, a total cost of 3 * 4 = 12 is incurred.

Example 3:

Input: source = “abcd”, target = “abce”, original = [“a”], changed = [“e”], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from ‘d’ to ‘e’.

Constraints:

1 <= source.length == target.length <= 105
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 106
original[i] != changed[i]

Complexity Analysis

Time Complexity: O(|\texttt{original}| + 26^3 + |\texttt{source}|)
Space Complexity: O(26^2 + |\texttt{source}|)

2976. Minimum Cost to Convert String I LeetCode Solution in C++

class Solution {
 public:
  long long minimumCost(string source, string target, vector<char>& original,
                        vector<char>& changed, vector<int>& cost) {
    long ans = 0;
    // dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    vector<vector<long>> dist(26, vector<long>(26, LONG_MAX));

    for (int i = 0; i < cost.size(); ++i) {
      const int u = original[i] - 'a';
      const int v = changed[i] - 'a';
      dist[u][v] = min(dist[u][v], static_cast<long>(cost[i]));
    }

    for (int k = 0; k < 26; ++k)
      for (int i = 0; i < 26; ++i)
        if (dist[i][k] < LONG_MAX)
          for (int j = 0; j < 26; ++j)
            if (dist[k][j] < LONG_MAX)
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 0; i < source.length(); ++i) {
      if (source[i] == target[i])
        continue;
      const int u = source[i] - 'a';
      const int v = target[i] - 'a';
      if (dist[u][v] == LONG_MAX)
        return -1;
      ans += dist[u][v];
    }

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

2976. Minimum Cost to Convert String I LeetCode Solution in Java

class Solution {
  public long minimumCost(String source, String target, char[] original, char[] changed,
                          int[] cost) {
    long ans = 0;
    // dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    long[][] dist = new long[26][26];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Long.MAX_VALUE));

    for (int i = 0; i < cost.length; ++i) {
      final int u = original[i] - 'a';
      final int v = changed[i] - 'a';
      dist[u][v] = Math.min(dist[u][v], cost[i]);
    }

    for (int k = 0; k < 26; ++k)
      for (int i = 0; i < 26; ++i)
        if (dist[i][k] < Long.MAX_VALUE)
          for (int j = 0; j < 26; ++j)
            if (dist[k][j] < Long.MAX_VALUE)
              dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 0; i < source.length(); ++i) {
      if (source.charAt(i) == target.charAt(i))
        continue;
      final int u = source.charAt(i) - 'a';
      final int v = target.charAt(i) - 'a';
      if (dist[u][v] == Long.MAX_VALUE)
        return -1;
      ans += dist[u][v];
    }

    return ans;
  }
}
// code provided by PROGIEZ

2976. Minimum Cost to Convert String I LeetCode Solution in Python

class Solution:
  def minimumCost(
      self,
      source: str,
      target: str,
      original: list[str],
      changed: list[str],
      cost: list[int],
  ) -> int:
    ans = 0
    # dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    dist = [[math.inf] * 26 for _ in range(26)]

    for a, b, c in zip(original, changed, cost):
      u = ord(a) - ord('a')
      v = ord(b) - ord('a')
      dist[u][v] = min(dist[u][v], c)

    for k in range(26):
      for i in range(26):
        if dist[i][k] < math.inf:
          for j in range(26):
            if dist[k][j] < math.inf:
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    for s, t in zip(source, target):
      if s == t:
        continue
      u = ord(s) - ord('a')
      v = ord(t) - ord('a')
      if dist[u][v] == math.inf:
        return -1
      ans += dist[u][v]

    return ans
 # code by PROGIEZ

Additional Resources

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

Table of Contents