Watch 10 video solutions for Minimum Cost to Convert String II, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by codestorywithMIK has 7,705 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 characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.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 "abcd" to "acbe", do the following operations: - Change substring source[1..1] from "b" to "c" at a cost of 5. - Change substring source[2..2] from "c" to "e" at a cost of 1. - Change substring source[2..2] from "e" to "b" at a cost of 2. - Change substring source[3..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 = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5] Output: 9 Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations: - Change substring source[1..3] from "bcd" to "cde" at a cost of 1. - Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation. - Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation. The total cost incurred is 1 + 3 + 5 = 9. It can be shown that this is the minimum possible cost.
Example 3:
Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578] Output: -1 Explanation: It is impossible to convert "abcdefgh" to "addddddd". If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation. If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
Constraints:
1 <= source.length == target.length <= 1000source, target consist only of lowercase English characters.1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i], changed[i] consist only of lowercase English characters.original[i] != changed[i]1 <= cost[i] <= 106Problem Overview: You receive two strings source and target plus a list of substring conversions where original[i] can be turned into changed[i] with a cost. Conversions can be chained, and you must transform source into target with the minimum total cost.
Approach 1: Dynamic Programming + Trie + Shortest Path (Time: O(n·L + k^3), Space: O(k^2 + n))
The key challenge is that substring conversions can chain together, meaning converting a → b → c might be cheaper than a direct rule. First treat each unique pattern from original and changed as a node in a graph. Build edges from original[i] to changed[i] with weight cost[i], then run an all‑pairs shortest path algorithm such as Floyd–Warshall to compute the minimum conversion cost between every pair of patterns. Next, store the patterns in a Trie so you can quickly match substrings while scanning the strings. Use dynamic programming where dp[i] represents the minimum cost to convert the first i characters. From each position i, walk both the source and target through the Trie simultaneously to find valid substring pairs and update dp[j]. This combines Dynamic Programming, Trie, and Shortest Path techniques to efficiently evaluate all valid conversions.
Approach 2: DFS with Memoization (Time: O(n·L + states), Space: O(n + recursion))
A top‑down variant treats the problem as a recursive search over the string index. Starting at position i, try every substring conversion that matches the current prefix of source and the corresponding part of target. For each valid segment, recursively compute the cost of converting the remaining suffix. Memoize results for each index so the same suffix is never recomputed. As with the DP approach, shortest conversion costs between patterns must be precomputed using a graph algorithm. This version is often easier to implement in Python but can be slightly slower due to recursion overhead and repeated substring checks.
Recommended for interviews: The bottom‑up dynamic programming approach with Trie matching and precomputed shortest paths is the most robust solution. Interviewers want to see that you model substring transformations as a graph problem and combine it with DP over string positions. Explaining the brute reasoning (trying every substring) shows understanding, while optimizing with Trie lookups and shortest path preprocessing demonstrates strong algorithmic design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming + Trie + Shortest Path | O(n·L + k^3) | O(k^2 + n) | Best general solution when many substring rules exist and chaining conversions is allowed |
| DFS with Memoization | O(n·L + states) | O(n) | Simpler top‑down implementation, good for Python when recursion depth is manageable |