2976. Minimum Cost to Convert String I
Medium
You are given two 0indexed strings source
and target
, both of length n
and consisting of lowercase English letters. You are also given two 0indexed 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: o 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 <= 10^{5}

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] <= 10^{6}
original[i] != changed[i]
Hint:
 Construct a graph with each letter as a node, and construct an edge
(a, b)
with weightc
if we can change from charactera
to letterb
with costc
. (Keep the one with the smallest cost in case there are multiple edges betweena
andb
).  Calculate the shortest path for each pair of characters
(source[i], target[i])
. The sum of cost over alli
in the range[0, source.length  1]
. If there is no path betweensource[i]
andtarget[i]
, the answer is1
.  Any shortest path algorithms will work since we only have
26
nodes. Since we only have at most26 * 26
pairs, we can save the result to avoid recalculation.  We can also use Floyd Warshall's algorithm to precompute all the results.
Solution:
To solve this problem, we'll use a graphbased approach. Specifically, we'll build a graph where each character is a node, and there's a directed edge from one character to another if we can convert the former to the latter at a given cost. We will then use the FloydWarshall algorithm to find the shortest paths between all pairs of characters, which will help us determine the minimum cost to convert each character in the source
string to the corresponding character in the target
string.
Here is the PHP code implementing this solution: 2976. Minimum Cost to Convert String I
<?php
// Example usage:
$source1 = "abcd";
$target1 = "acbe";
$original1 = ["a","b","c","c","e","d"];
$changed1 = ["b","c","b","e","b","e"];
$cost1 = [2,5,5,1,2,20];
echo minimumCost($source1, $target1, $original1, $changed1, $cost1); // Output: 28
$source2 = "aaaa";
$target2 = "bbbb";
$original2 = ["a","c"];
$changed2 = ["c","b"];
$cost2 = [1,2];
echo minimumCost($source2, $target2, $original2, $changed2, $cost2); // Output: 12
$source3 = "abcd";
$target3 = "abce";
$original3 = ["a"];
$changed3 = ["e"];
$cost3 = [10000];
echo minimumCost($source3, $target3, $original3, $changed3, $cost3); // Output: 1
?>
Explanation:

Graph Initialization:
 We initialize a 26x26 matrix (
graph
) where each element represents the cost to convert one character to another. Initially, we set all costs to a large number ($inf
) except for the diagonal elements, which we set to 0 because converting a character to itself has no cost.
 We initialize a 26x26 matrix (

Graph Population:
 We fill the graph with the given transformation costs. If multiple costs are given for the same transformation, we take the minimum cost.

FloydWarshall Algorithm:
 This algorithm computes the shortest paths between all pairs of nodes. After running this algorithm,
graph[i][j]
will contain the minimum cost to convert characteri
to characterj
.
 This algorithm computes the shortest paths between all pairs of nodes. After running this algorithm,

Conversion Cost Calculation:
 For each character in the
source
string, we find the cost to convert it to the corresponding character in thetarget
string using our precomputedgraph
. If any conversion is impossible (indicated by a cost of$inf
), we return 1. Otherwise, we sum up all the conversion costs to get the total minimum cost.
 For each character in the
This approach ensures that we efficiently compute the minimum conversion cost, even for large input sizes.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)