2976. 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]

Approach 01

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

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

        // Initialize the distance matrix with the given costs
        for (int i = 0; i < cost.size(); ++i) {
            const int sourceChar = original[i] - 'a';
            const int targetChar = changed[i] - 'a';
            distanceMatrix[sourceChar][targetChar] = min(distanceMatrix[sourceChar][targetChar], static_cast<long>(cost[i]));
        }

        // Apply the Floyd-Warshall algorithm to compute the shortest paths between all pairs of characters
        for (int intermediate = 0; intermediate < 26; ++intermediate) {
            for (int start = 0; start < 26; ++start) {
                if (distanceMatrix[start][intermediate] < LONG_MAX) {
                    for (int end = 0; end < 26; ++end) {
                        if (distanceMatrix[intermediate][end] < LONG_MAX) {
                            distanceMatrix[start][end] = min(distanceMatrix[start][end], distanceMatrix[start][intermediate] + distanceMatrix[intermediate][end]);
                        }
                    }
                }
            }
        }

        // Calculate the total minimum cost to change the source string to the target string
        for (int i = 0; i < source.length(); ++i) {
            if (source[i] == target[i]) {
                continue;
            }
            const int sourceChar = source[i] - 'a';
            const int targetChar = target[i] - 'a';
            if (distanceMatrix[sourceChar][targetChar] == LONG_MAX) {
                return -1;
            }
            totalCost += distanceMatrix[sourceChar][targetChar];
        }

        return totalCost;
    }
};

from typing import List

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        totalCost = 0
        # distanceMatrix[u][v] represents the minimum cost to change character ('a' + u) to character ('a' + v)
        distanceMatrix = [[float('inf')] * 26 for _ in range(26)]

        # Initialize the distance matrix with the given costs
        for i in range(len(cost)):
            sourceChar = ord(original[i]) - ord('a')
            targetChar = ord(changed[i]) - ord('a')
            distanceMatrix[sourceChar][targetChar] = min(distanceMatrix[sourceChar][targetChar], cost[i])

        # Apply the Floyd-Warshall algorithm to compute the shortest paths between all pairs of characters
        for intermediate in range(26):
            for start in range(26):
                if distanceMatrix[start][intermediate] < float('inf'):
                    for end in range(26):
                        if distanceMatrix[intermediate][end] < float('inf'):
                            distanceMatrix[start][end] = min(distanceMatrix[start][end], distanceMatrix[start][intermediate] + distanceMatrix[intermediate][end])

        # Calculate the total minimum cost to change the source string to the target string
        for i in range(len(source)):
            if source[i] == target[i]:
                continue
            sourceChar = ord(source[i]) - ord('a')
            targetChar = ord(target[i]) - ord('a')
            if distanceMatrix[sourceChar][targetChar] == float('inf'):
                return -1
            totalCost += distanceMatrix[sourceChar][targetChar]

        return totalCost

Time Complexity

• Initialization of the Distance Matrix:

  The initialization of the distance matrix involves setting initial costs based on the input vectors, which takes \( O(m) \) time, where m is the size of the cost vector.

• Floyd-Warshall Algorithm:

  The Floyd-Warshall algorithm is applied to compute the shortest paths between all pairs of characters. This involves three nested loops over the 26 characters, leading to a time complexity of \( O(26^3) \), which simplifies to \( O(1) \) since 26 is a constant.

• Calculating Total Minimum Cost:

  Iterating over the characters of the source and target strings to calculate the total cost takes \( O(n) \) time, where n is the length of the source string.

• Overall Time Complexity:

  The overall time complexity is \( O(m + n) \) since the Floyd-Warshall algorithm’s complexity is constant.

Space Complexity

• Distance Matrix:

  The distance matrix is a 2D vector of size 26×26, leading to a space complexity of \( O(1) \) as 26 is a constant.

• Other Variables:

  Other variables such as totalCost, sourceChar, targetChar, and intermediate values used for computation take \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).