Watch 10 video solutions for Minimum Cost to Convert String I, a medium level problem involving Array, String, Graph. This walkthrough by codestorywithMIK has 15,156 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, target consist 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]Problem Overview: You are given two strings source and target of equal length and a list of character transformations with associated costs. Each operation converts one character into another. The goal is to compute the minimum total cost to transform source into target. If any position cannot be converted through the given rules, return -1.
Approach 1: Graph Based Shortest Path (O(V * E), Space O(V + E))
Treat each character as a node in a directed weighted graph. Each transformation rule a -> b with cost c becomes an edge. For every character pair needed in the strings, compute the shortest path from the source character to the target character. A simple shortest-path traversal from each starting character accumulates the minimal conversion cost. This works because character conversions may require intermediate steps such as a -> c -> d. The approach models the problem directly as a graph traversal.
Approach 2: Dynamic Programming with Floyd-Warshall (O(26^3), Space O(26^2))
Since the alphabet size is fixed (26 lowercase letters), compute the minimum conversion cost between every pair of characters using the Floyd–Warshall algorithm. Initialize a 26 x 26 matrix with direct transformation costs, then iteratively update using the relation dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). This dynamic programming approach efficiently finds the shortest paths between all pairs of nodes in a shortest path problem. After preprocessing, iterate through the strings and sum the cost for each character conversion.
Approach 3: Graph-based Approach with Dijkstra's Algorithm (O(26 * (E log V)), Space O(V + E))
Build a weighted adjacency list for character transformations and run Dijkstra's algorithm from each character that appears in source. Dijkstra guarantees the optimal path in graphs with non-negative weights. Cache the computed shortest distances so repeated conversions reuse the result. This approach scales well if the transformation rules grow larger and mirrors typical interview solutions for weighted graph problems.
Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path (O(26^3), Space O(26^2))
This is the most direct solution when the node set is small and fixed. Precompute minimal costs between every pair of characters using the Floyd–Warshall all-pairs algorithm. Once the matrix is ready, each string position becomes a constant-time lookup. The overall runtime is dominated by the preprocessing step, which remains effectively constant due to the small alphabet size.
Recommended for interviews: Floyd–Warshall is usually the cleanest answer because the character set is limited to 26 nodes. Interviewers like this observation because it reduces repeated shortest-path searches into a single preprocessing step. Explaining the graph model first shows strong problem understanding, while implementing the Floyd–Warshall optimization demonstrates algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Based Shortest Path | O(V * E) | O(V + E) | When modeling the problem directly as a graph and computing paths per character |
| Dynamic Programming with Floyd-Warshall | O(26^3) | O(26^2) | Best when the alphabet size is small and fixed |
| Graph + Dijkstra | O(26 * (E log V)) | O(V + E) | Useful when transformation rules form a larger weighted graph |
| Floyd-Warshall All-Pairs Shortest Path | O(26^3) | O(26^2) | Optimal interview solution due to constant alphabet size |