Minimum Cost to Convert String I
MedPrompt
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 <= 105source,targetconsist of lowercase English letters.1 <= cost.length == original.length == changed.length <= 2000original[i],changed[i]are lowercase English letters.1 <= cost[i] <= 106original[i] != changed[i]
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the character conversions as a directed weighted graph where characters are nodes and conversions are edges. For each required transformation from a character u to v, it runs Dijkstra's algorithm starting from u to find the shortest path (minimum cost) to v. To avoid re-computation, the results of Dijkstra's algorithm are cached.
Algorithm
- Create an adjacency list to represent the character conversion graph. The 26 lowercase letters are the nodes.
- For each
(original[i], changed[i], cost[i]), add a directed edge fromoriginal[i]tochanged[i]with weightcost[i]. - Initialize a
minCost[26][26]matrix with a sentinel value (e.g., -1) to cache shortest path costs. - Initialize
totalCost = 0. - Iterate through
sourceandtargetfromi = 0ton-1. - Let
u = source.charAt(i)andv = target.charAt(i). - If
u == v, continue. - If
minCost[u][v]is not yet computed, run Dijkstra's algorithm starting from nodeu.- Dijkstra's finds the shortest paths from
uto all other nodes. - Store these computed costs in the
minCost[u]row.
- Dijkstra's finds the shortest paths from
- After ensuring
minCost[u][v]is computed, check its value. - If
minCost[u][v]is infinity, it's impossible to convert. Return -1. - Otherwise, add
minCost[u][v]tototalCost. - After the loop, return
totalCost.
Walkthrough
We first construct a graph where the 26 lowercase letters are the vertices. For each entry in original, changed, and cost, we add a directed edge from original[i] to changed[i] with weight cost[i]. This can be represented using an adjacency list.
We then iterate through the source and target strings. For each index i where source[i] differs from target[i], we need to find the minimum cost to convert source[i] to target[i].
This is a shortest path problem on the graph. We can use Dijkstra's algorithm. To optimize, we can use memoization. We maintain a 2D array, say minCost[26][26], to store the shortest path costs.
When we need the cost from character u to v, we first check our minCost table. If the value is already computed, we use it. If not, we run Dijkstra's algorithm starting from u. This computes the shortest paths from u to all other characters. We store all these results in our minCost table for future use.
The total cost is the sum of these minimum costs for all i. If any required conversion is impossible (no path exists), we return -1.
import java.util.*; class Solution { public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { List<int[]>[] adj = new ArrayList[26]; for (int i = 0; i < 26; i++) { adj[i] = new ArrayList<>(); } for (int i = 0; i < original.length; i++) { adj[original[i] - 'a'].add(new int[]{changed[i] - 'a', cost[i]}); } long[][] minCost = new long[26][26]; for (int i = 0; i < 26; i++) { Arrays.fill(minCost[i], -1L); } long totalCost = 0; for (int i = 0; i < source.length(); i++) { int u = source.charAt(i) - 'a'; int v = target.charAt(i) - 'a'; if (u == v) { continue; } if (minCost[u][v] == -1L) { dijkstra(u, adj, minCost[u]); } if (minCost[u][v] == Long.MAX_VALUE) { return -1; } totalCost += minCost[u][v]; } return totalCost; } private void dijkstra(int startNode, List<int[]>[] adj, long[] costs) { PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); pq.offer(new long[]{0, startNode}); Arrays.fill(costs, Long.MAX_VALUE); costs[startNode] = 0; while (!pq.isEmpty()) { long[] current = pq.poll(); long currentCost = current[0]; int u = (int) current[1]; if (currentCost > costs[u]) { continue; } for (int[] edge : adj[u]) { int v = edge[0]; int weight = edge[1]; if (costs[u] != Long.MAX_VALUE && costs[u] + weight < costs[v]) { costs[v] = costs[u] + weight; pq.offer(new long[]{costs[v], v}); } } } }}Complexity
Time
O(M + N + C * (E + V log V)), where N is the length of the strings, M is the length of `original`/`cost` arrays, V is the number of characters (26), E is the number of conversion rules (at most M), and C is the number of unique characters in `source` (at most 26). Since V is a small constant, this simplifies to O(M + N + C * E). In the worst case C=26, so the complexity is dominated by O(M+N) with a larger constant factor for the graph algorithm part.
Space
O(V^2 + E), where V is the number of characters (26) and E is the number of conversion rules. V^2 is for the memoization table and E is for the adjacency list. Since V is a constant, this simplifies to O(E).
Trade-offs
Pros
Conceptually straightforward application of a standard graph algorithm.
It's a 'lazy' approach, only computing shortest paths as they are needed. If the source string only contains a few distinct characters, we run Dijkstra's fewer times.
Cons
Can be less efficient than pre-computing all-pairs shortest paths if many different source characters are present.
The overhead of the priority queue in Dijkstra's can be larger than the simple loops of Floyd-Warshall for a small, dense graph.
The implementation is slightly more complex due to managing the cache and calls to Dijkstra's.
Solutions
Solution
class Solution {public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { final int inf = 1 << 29; int[][] g = new int[26][26]; for (int i = 0; i < 26; ++i) { Arrays.fill(g[i], inf); g[i][i] = 0; } for (int i = 0; i < original.length; ++i) { int x = original[i] - 'a'; int y = changed[i] - 'a'; int z = cost[i]; g[x][y] = Math.min(g[x][y], z); } for (int k = 0; k < 26; ++k) { for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]); } } } long ans = 0; int n = source.length(); for (int i = 0; i < n; ++i) { int x = source.charAt(i) - 'a'; int y = target.charAt(i) - 'a'; if (x != y) { if (g[x][y] >= inf) { return -1; } ans += g[x][y]; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.