Minimum Cost to Convert String I — Problem & Solution
Minimum Cost to Convert String I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Cost to Convert String I is a medium coding problem on arrays, strings and graph, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Graph, Shortest Path
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings source and target of the same length, both of lowercase English letters, and three arrays original, changed and cost of the same length. Each original[i] and changed[i] is a single lowercase letter.
In one operation you may change a character x of the current string into y at a cost of z if there is an index j with original[j] == x, changed[j] == y and cost[j] == z. Operations may be repeated any number of times, on any positions.
Return the minimum total cost of turning source into target, or -1 if it is impossible.
CodeKairo bounds the string length and the costs (see the constraints) so the total always fits in a 32-bit integer.
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: a stays a; b → c costs 5; c → b is cheapest as c → e → b for 1 + 2 = 3; d → e costs 20. Total 5 + 3 + 20 = 28.
Example 2
Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: Each a becomes b through c for 1 + 2 = 3; four positions cost 12.
Example 3
Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [1000]
Output: -1
Explanation: No rule ever turns a d into an e.
Constraints
1 <= source.length == target.length <= 10^4source and target consist of lowercase English letters1 <= cost.length == original.length == changed.length <= 2000original[i] and changed[i] are lowercase English letters1 <= cost[i] <= 10^3original[i] != changed[i]
Hints for Minimum Cost to Convert String I
Hint 1
Each position is independent: the total is the sum, over positions, of the cheapest way to turn
source[i]intotarget[i].Hint 2
Treat the 26 letters as nodes of a weighted directed graph with an edge
original[j] → changed[j]of weightcost[j](keep the cheapest of parallel rules). The cheapest conversion is a shortest path.Hint 3
With only 26 nodes, Floyd–Warshall gives every letter-to-letter cost at once; then sum up, returning
-1as soon as some needed pair is unreachable.
How to solve Minimum Cost to Convert String I
Conversions of different positions never interact, so the problem reduces to the cheapest letter-to-letter conversion — an all-pairs shortest path on a 26-node graph — summed over the positions.
Approach
- Initialise
dist[x][x] = 0anddist[x][y] = ∞otherwise; for each rule setdist[o][c] = min(dist[o][c], cost). - Run Floyd–Warshall over the 26 letters.
- For each position
i, adddist[source[i]][target[i]]; if it is∞, return-1. - Return the sum.
Why it works
A sequence of operations applied to one position is a walk in the letter graph from source[i] to target[i] whose cost is the sum of its edge weights, and the cheapest such walk is a shortest path. Positions do not share any resource, so minimising each one separately minimises the total.
Complexity
- Time —
O(26³ + m + n) - Space —
O(26²)
Pitfalls
- Several rules can join the same pair of letters with different costs — keep the cheapest.
- Positions where
source[i] == target[i]cost nothing. - In the original problem the total can exceed 32 bits; CodeKairo's bounds keep it below
2.5 · 10^8.
Reference solution
Python
from typing import List
def minimumCost(source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
INF = float("inf")
d = [[0 if i == j else INF for j in range(26)] for i in range(26)]
for o, c, w in zip(original, changed, cost):
a, b = ord(o) - 97, ord(c) - 97
if w < d[a][b]:
d[a][b] = w
for k in range(26):
dk = d[k]
for i in range(26):
di = d[i]
dik = di[k]
if dik == INF:
continue
for j in range(26):
if dik + dk[j] < di[j]:
di[j] = dik + dk[j]
total = 0
for s, t in zip(source, target):
w = d[ord(s) - 97][ord(t) - 97]
if w == INF:
return -1
total += w
return totalJava
public static int minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {
final int INF = 1000000000;
int[][] d = new int[26][26];
for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) d[i][j] = i == j ? 0 : INF;
for (int r = 0; r < original.length; r++) {
int a = original[r].charAt(0) - 'a', b = changed[r].charAt(0) - 'a';
d[a][b] = Math.min(d[a][b], cost[r]);
}
for (int k = 0; k < 26; k++)
for (int x = 0; x < 26; x++) {
if (d[x][k] == INF) continue;
for (int y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
}
long total = 0;
for (int p = 0; p < source.length(); p++) {
int w = d[source.charAt(p) - 'a'][target.charAt(p) - 'a'];
if (w == INF) return -1;
total += w;
}
return (int) total;
}C++
int minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
const int INF = 1000000000;
vector<vector<int>> d(26, vector<int>(26, INF));
for (int i = 0; i < 26; i++) d[i][i] = 0;
for (size_t r = 0; r < original.size(); r++) {
int a = original[r][0] - 'a', b = changed[r][0] - 'a';
d[a][b] = min(d[a][b], cost[r]);
}
for (int k = 0; k < 26; k++)
for (int x = 0; x < 26; x++) {
if (d[x][k] == INF) continue;
for (int y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
}
long long total = 0;
for (size_t p = 0; p < source.size(); p++) {
int w = d[source[p] - 'a'][target[p] - 'a'];
if (w == INF) return -1;
total += w;
}
return (int) total;
}JavaScript
var minimumCost = function(source, target, original, changed, cost) {
var INF = 1000000000;
var d = [];
for (var i = 0; i < 26; i++) { d.push([]); for (var j = 0; j < 26; j++) d[i].push(i === j ? 0 : INF); }
for (var r = 0; r < original.length; r++) {
var a = original[r].charCodeAt(0) - 97, b = changed[r].charCodeAt(0) - 97;
if (cost[r] < d[a][b]) d[a][b] = cost[r];
}
for (var k = 0; k < 26; k++)
for (var x = 0; x < 26; x++) {
if (d[x][k] === INF) continue;
for (var y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
}
var total = 0;
for (var p = 0; p < source.length; p++) {
var w = d[source.charCodeAt(p) - 97][target.charCodeAt(p) - 97];
if (w === INF) return -1;
total += w;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.