DSA problem

Minimum Cost to Convert String I

MediumShortest PathPattern: Shortest Pathtop600AmazonGoogleMicrosoft

You are given two strings source and target, both of equal length, and three parallel arrays original, changed, and cost. Each triple (original[i], changed[i], cost[i]) means you may convert any occurrence of the single character original[i] into changed[i] at a price of cost[i]. You may apply any conversion any number of times in any order. Return the minimum total cost to transform source into target, or -1 if it is impossible.

The crucial observation is that the 26 lowercase letters form the vertices of a directed weighted graph, where each triple (o, c, w) is a directed edge o → c of weight w. Several triples may describe the same edge with different costs; we keep only the cheapest. The cost of changing a single character a into b is then the length of the shortest path from a to b in this 26-node graph, or infinity if no such path exists.

Because the graph has only 26 nodes, we can afford an all-pairs shortest path computation. The cleanest tool is Floyd-Warshall: initialize a 26 × 26 matrix dist with infinities and zeros on the diagonal, fold in each edge with the minimum cost, then relax through every intermediate node k. After the triple loop dist[a][b] holds the cheapest way to convert a into b.

To compute the answer, scan source and target in parallel: whenever the two strings disagree at position i, accumulate dist[source[i]][target[i]]. If any required conversion has cost infinity, the entire transformation is impossible and we return -1. The total runtime is O(E + 26³ + n) — dominated by the Floyd-Warshall step — with constant extra space beyond the matrix itself.

Examples

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: b→c costs 5, c→e costs 1, e→b costs 2 (or 7), and d→e costs 20. Summing the minimum conversion costs at the differing positions yields 28.

Example 2

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]

Output: 12

Explanation: Each 'a' becomes 'b' via the path a→c→b at cost 3, and there are four such conversions for a total of 12.

Example 3

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]

Output: -1

Explanation: There is no path from 'd' to 'e' in the conversion graph, so the transformation is impossible.

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]

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

graphshortest-pathfloyd-warshallstring

Browse all DSA problems