# Minimum Cost to Convert String II **Difficulty:** HARD [External](https://leetcode.com/problems/minimum-cost-to-convert-string-ii) Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-convert-string-ii **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path) **Data structures:** Array, String, Trie, Graph **Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian) --- ## Problem 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: * The substrings picked in the operations are `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**. * The substrings picked in the operations are `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 <= 1000` * `source`, `target` consist only of lowercase English characters. * `1 <= cost.length == original.length == changed.length <= 100` * `1 <= original[i].length == changed[i].length <= source.length` * `original[i]`, `changed[i]` consist only of lowercase English characters. * `original[i] != changed[i]` * `1 <= cost[i] <= 106` # Approaches ## Dynamic Programming with Naive Substring Matching This approach uses dynamic programming to solve the problem. We define `dp[i]` as the minimum cost to convert the prefix `source[0...i-1]` to `target[0...i-1]`. The final answer will be `dp[n]`, where `n` is the length of the strings. The core of the problem is to determine the cost of transforming one substring to another. Since multiple transformations can be applied to the same substring, this subproblem can be modeled as finding the shortest path in a graph. The nodes of the graph are the unique strings from `original` and `changed`, and the edges are the given transformations with their costs. We can pre-compute all-pairs shortest paths using the Floyd-Warshall algorithm. This gives us the minimum cost to convert any transformable string `u` to another string `v`. With the transformation costs pre-computed, we can build our DP solution. The transition for `dp[i]` considers all possible last operations. An operation could transform a suffix `source[j...i-1]` to `target[j...i-1]`. We iterate through all possible start indices `j < i`, calculate the cost of this suffix transformation, and update `dp[i]` based on the cost for the prefix `dp[j]` plus the suffix transformation cost. This leads to a polynomial-time solution, but the repeated creation and lookup of substrings in each step make it less efficient. **Time:** O(U^3 + n^3), where `U` is the number of unique strings in `original` and `changed` (at most 200), and `n` is the length of `source`. The Floyd-Warshall part takes O(U^3). The DP part has two nested loops for `i` and `j`, and inside, substring operations and hash lookups take O(i-j) time, leading to an overall O(n^3) complexity for the DP part. · **Space:** O(U*L + U^2 + n), where `L` is the maximum length of a transformation string. This space is used for storing the unique strings (O(U*L)), the distance matrix for Floyd-Warshall (O(U^2)), and the DP array (O(n)). **Pros:** Conceptually straightforward application of dynamic programming.; Correctly solves the problem by breaking it down into subproblems.; The pre-computation step neatly handles the complex multi-step transformations on a single substring. **Cons:** The time complexity is high due to nested loops and repeated substring operations.; Substring creation and hash map lookups for strings can be time-consuming, leading to a complexity of O(n^3) or O(n^2 * L), which might be too slow for larger constraints. ### Explanation ### Algorithm 1. **Pre-computation of Transformation Costs:** * Collect all unique strings from `original` and `changed` arrays into a set. Let's say there are `U` unique strings. * Create a mapping from each unique string to an integer index from `0` to `U-1`. * Initialize a `U x U` adjacency matrix `dist` with infinity, where `dist[i][j]` will store the minimum cost to convert string `i` to string `j`. Set `dist[i][i] = 0`. * Populate `dist` with the initial costs from the input: for each `(original[k], changed[k], cost[k])`, set `dist[map(original[k])][map(changed[k])] = min(dist[map(original[k])][map(changed[k])], cost[k])`. * Run the Floyd-Warshall algorithm on the `dist` matrix to find all-pairs shortest paths. After this, `dist[i][j]` contains the minimum cost to transform string `i` to `j`. 2. **Dynamic Programming:** * Create a DP array `dp` of size `n+1`, initialized with a large value representing infinity. Set `dp[0] = 0`. * Iterate `i` from `1` to `n`: * For each `i`, iterate `j` from `0` to `i-1`. * Extract the substrings `s_sub = source.substring(j, i)` and `t_sub = target.substring(j, i)`. * Determine the cost of converting `s_sub` to `t_sub`. * If `s_sub.equals(t_sub)`, the cost is 0. * Otherwise, look up `s_sub` and `t_sub` in our string-to-index map. If both exist, the cost is `dist[map(s_sub)][map(t_sub)]`. * If they don't exist in the map, the conversion is impossible (cost is infinity). * If the conversion cost is not infinity and `dp[j]` is not infinity, update `dp[i] = min(dp[i], dp[j] + cost)`. 3. **Result:** * The final answer is `dp[n]`. If `dp[n]` is still infinity, it's impossible to convert, so return -1. ### Code Snippet ```java class Solution { public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) { // Step 1: Pre-computation with Floyd-Warshall Map strToIdx = new HashMap<>(); int idx = 0; for (String s : original) { if (!strToIdx.containsKey(s)) strToIdx.put(s, idx++); } for (String s : changed) { if (!strToIdx.containsKey(s)) strToIdx.put(s, idx++); } int numStrings = strToIdx.size(); long[][] dist = new long[numStrings][numStrings]; for (int i = 0; i < numStrings; i++) { Arrays.fill(dist[i], Long.MAX_VALUE); dist[i][i] = 0; } for (int i = 0; i < original.length; i++) { int u = strToIdx.get(original[i]); int v = strToIdx.get(changed[i]); dist[u][v] = Math.min(dist[u][v], (long)cost[i]); } for (int k = 0; k < numStrings; k++) { for (int i = 0; i < numStrings; i++) { for (int j = 0; j < numStrings; j++) { if (dist[i][k] != Long.MAX_VALUE && dist[k][j] != Long.MAX_VALUE) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } } // Step 2: Dynamic Programming int n = source.length(); long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { // Case 1: No operation on the last character if (source.charAt(i - 1) == target.charAt(i - 1)) { if (dp[i-1] != Long.MAX_VALUE) { dp[i] = dp[i-1]; } } // Case 2: An operation ends at i-1 for (int j = 0; j < i; j++) { String s_sub = source.substring(j, i); String t_sub = target.substring(j, i); if (dp[j] == Long.MAX_VALUE) continue; if (s_sub.equals(t_sub)) { dp[i] = Math.min(dp[i], dp[j]); } else { if (strToIdx.containsKey(s_sub) && strToIdx.containsKey(t_sub)) { int u = strToIdx.get(s_sub); int v = strToIdx.get(t_sub); if (dist[u][v] != Long.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + dist[u][v]); } } } } } return dp[n] == Long.MAX_VALUE ? -1 : dp[n]; } } ``` ### Algorithm - Collect all unique strings from `original` and `changed` and map them to indices. - Build a graph where these strings are nodes and transformations are edges with given costs. - Compute all-pairs shortest paths using the Floyd-Warshall algorithm to find the minimum cost to convert any string `u` to `v`. - Use dynamic programming where `dp[i]` is the minimum cost to convert `source[0...i-1]` to `target[0...i-1]`. - The DP transition is `dp[i] = min(dp[j] + cost(source[j...i-1] -> target[j...i-1]))` for all `0 <= j < i`. - The cost for substrings is 0 if they are equal, or the pre-computed shortest path cost if they are part of the transformation set. - The final answer is `dp[n]`, or -1 if `dp[n]` is infinity. ## Optimized Dynamic Programming with a Trie The previous DP approach can be optimized. The bottleneck is the inner loop where we generate all possible substrings `source[j...i-1]` and `target[j...i-1]` and look them up. This process is inefficient. We can significantly speed up the lookup of these substrings by using a Trie (prefix tree). We first build a Trie containing all unique strings from `original` and `changed`. Each node in the Trie that marks the end of a string will store the unique index of that string. Then, in our DP calculation for `dp[i]`, instead of iterating `j` from `0` to `i-1` and creating substrings, we can perform a single backward scan from `i-1` down to `0`. During this scan, we traverse our Trie based on the characters of `source` and `target`. This allows us to find all matching transformation strings ending at `i-1` efficiently. This optimization reduces the complexity of the DP calculation from O(n^3) to O(n^2), making the solution much faster and capable of passing within the time limits for the given constraints. **Time:** O(U^3 + U*L + n^2). The Floyd-Warshall part is O(U^3). Building the Trie takes O(U*L). The DP part now has a time complexity of O(n^2) because for each `i`, we do a single backward scan of at most `i` steps, and each step is O(1) for Trie traversal. · **Space:** O(U*L + U^2 + n). The space complexity is dominated by the same factors as the previous approach: storing unique strings, the Floyd-Warshall distance matrix, the Trie (which is also O(U*L)), and the DP array. **Pros:** Highly efficient, with a time complexity that fits within typical contest limits.; The Trie eliminates the expensive repeated substring creation and hashing of the naive DP approach.; It's a robust solution combining graph algorithms (Floyd-Warshall) and string algorithms (Trie) with dynamic programming. **Cons:** More complex to implement due to the addition of the Trie data structure.; The logic for the backward scan and Trie traversal requires careful implementation to be correct. ### Explanation ### Algorithm 1. **Pre-computation of Transformation Costs:** * This step is identical to the previous approach. We use Floyd-Warshall to compute the all-pairs shortest paths for the transformation strings, storing the results in a `dist` matrix. 2. **Trie Construction:** * Create a Trie data structure. * Insert all unique strings from `original` and `changed` into the Trie. * Each node in the Trie will have an array of children (for each character 'a'-'z'). * Each node will also have a field, say `stringIndex`, initialized to -1. When a string is inserted, the `stringIndex` of its final node is set to the string's unique mapped index. 3. **Optimized Dynamic Programming:** * Create a DP array `dp` of size `n+1`, initialized with infinity. Set `dp[0] = 0`. * Iterate `i` from `1` to `n`: * First, handle the simple case: if `source[i-1] == target[i-1]`, we can potentially extend the solution from `dp[i-1]`. So, `dp[i] = dp[i-1]`. * To handle transformations, start a backward scan from `j = i-1` down to `0`. Maintain two pointers to Trie nodes, `s_node` for `source` and `t_node` for `target`, both starting at the Trie's root. * In each step of the backward scan (for `j`), advance `s_node` and `t_node` according to `source.charAt(j)` and `target.charAt(j)`. * If at any point either pointer becomes null, it means no further transformation strings can be matched, so we can break the backward scan. * If both `s_node` and `t_node` represent the end of some transformation strings (i.e., their `stringIndex` is not -1), it means we've found a valid transformation for `source[j...i-1]` to `target[j...i-1]`. * We then use the pre-computed cost `dist[s_node.stringIndex][t_node.stringIndex]` to update `dp[i] = min(dp[i], dp[j] + cost)`. * We also need to handle the case where `source[j...i-1] == target[j...i-1]`. This can be done in the same backward loop by tracking if the suffix is identical. If it is, we can update `dp[i] = min(dp[i], dp[j])`. 4. **Result:** * The final answer is `dp[n]`, or -1 if it remains infinity. ### Code Snippet ```java class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; int index = -1; } public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) { // Step 1: Pre-computation with Floyd-Warshall Map strToIdx = new HashMap<>(); int idx = 0; for (String s : original) if (!strToIdx.containsKey(s)) strToIdx.put(s, idx++); for (String s : changed) if (!strToIdx.containsKey(s)) strToIdx.put(s, idx++); int numStrings = strToIdx.size(); long[][] dist = new long[numStrings][numStrings]; for (int i = 0; i < numStrings; i++) { Arrays.fill(dist[i], Long.MAX_VALUE); dist[i][i] = 0; } for (int i = 0; i < original.length; i++) { int u = strToIdx.get(original[i]); int v = strToIdx.get(changed[i]); dist[u][v] = Math.min(dist[u][v], (long)cost[i]); } for (int k = 0; k < numStrings; k++) { for (int i = 0; i < numStrings; i++) { for (int j = 0; j < numStrings; j++) { if (dist[i][k] != Long.MAX_VALUE && dist[k][j] != Long.MAX_VALUE) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } } // Step 2: Build Trie TrieNode root = new TrieNode(); for (String s : strToIdx.keySet()) { TrieNode curr = root; for (char c : s.toCharArray()) { if (curr.children[c - 'a'] == null) { curr.children[c - 'a'] = new TrieNode(); } curr = curr.children[c - 'a']; } curr.index = strToIdx.get(s); } // Step 3: Optimized DP int n = source.length(); long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { if (dp[i-1] != Long.MAX_VALUE) { if (source.charAt(i-1) == target.charAt(i-1)) { dp[i] = Math.min(dp[i], dp[i-1]); } } TrieNode sNode = root; TrieNode tNode = root; for (int j = i - 1; j >= 0; j--) { sNode = sNode.children[source.charAt(j) - 'a']; tNode = tNode.children[target.charAt(j) - 'a']; if (sNode == null || tNode == null) break; if (sNode.index != -1 && tNode.index != -1) { if (dp[j] != Long.MAX_VALUE) { long conversionCost = dist[sNode.index][tNode.index]; if (conversionCost != Long.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + conversionCost); } } } } } return dp[n] == Long.MAX_VALUE ? -1 : dp[n]; } } ``` ### Algorithm - Pre-compute all-pairs shortest paths for transformation costs using Floyd-Warshall, same as the previous approach. - Build a Trie and insert all unique transformation strings. The terminal node for each string stores its unique index. - Use dynamic programming where `dp[i]` is the minimum cost for `source[0...i-1]`. - To compute `dp[i]`, perform a backward scan from `i-1` down to `0`. In this scan, traverse the Trie for both `source` and `target` suffixes. - If a suffix `source[j...i-1]` and `target[j...i-1]` both match strings in the Trie, use their pre-computed transformation cost to update `dp[i]` from `dp[j]`. - Also handle the case where `source[i-1] == target[i-1]` for a zero-cost transition. - The final answer is `dp[n]`. # Solutions ### Java ```java class Node { Node [] children = new Node [ 26 ]; int v = - 1 ; } class Solution { private final long inf = 1L << 60 ; private Node root = new Node (); private int idx ; private long [][] g ; private char [] s ; private char [] t ; private Long [] f ; public long minimumCost ( String source , String target , String [] original , String [] changed , int [] cost ) { int m = cost . length ; g = new long [ m << 1 ][ m << 1 ]; s = source . toCharArray (); t = target . toCharArray (); for ( int i = 0 ; i < g . length ; ++ i ) { Arrays . fill ( g [ i ], inf ); g [ i ][ i ] = 0 ; } for ( int i = 0 ; i < m ; ++ i ) { int x = insert ( original [ i ]); int y = insert ( changed [ i ]); g [ x ][ y ] = Math . min ( g [ x ][ y ], cost [ i ]); } for ( int k = 0 ; k < idx ; ++ k ) { for ( int i = 0 ; i < idx ; ++ i ) { if ( g [ i ][ k ] >= inf ) { continue ; } for ( int j = 0 ; j < idx ; ++ j ) { g [ i ][ j ] = Math . min ( g [ i ][ j ], g [ i ][ k ] + g [ k ][ j ]); } } } f = new Long [ s . length ]; long ans = dfs ( 0 ); return ans >= inf ? - 1 : ans ; } private int insert ( String w ) { Node node = root ; for ( char c : w . toCharArray ()) { int i = c - 'a' ; if ( node . children [ i ] == null ) { node . children [ i ] = new Node (); } node = node . children [ i ]; } if ( node . v < 0 ) { node . v = idx ++; } return node . v ; } private long dfs ( int i ) { if ( i >= s . length ) { return 0 ; } if ( f [ i ] != null ) { return f [ i ]; } long res = s [ i ] == t [ i ] ? dfs ( i + 1 ) : inf ; Node p = root , q = root ; for ( int j = i ; j < s . length ; ++ j ) { p = p . children [ s [ j ] - 'a' ]; q = q . children [ t [ j ] - 'a' ]; if ( p == null || q == null ) { break ; } if ( p . v < 0 || q . v < 0 ) { continue ; } long t = g [ p . v ][ q . v ]; if ( t < inf ) { res = Math . min ( res , t + dfs ( j + 1 )); } } return f [ i ] = res ; } } ``` ### CPP ```cpp class Node { public: Node * children [ 26 ]; int v = - 1 ; Node () { fill ( children , children + 26 , nullptr ); } }; class Solution { private: const long long inf = 1LL << 60 ; Node * root = new Node (); int idx ; vector < vector < long long >> g ; string s ; string t ; vector < long long > f ; public: long long minimumCost ( string source , string target , vector < string >& original , vector < string >& changed , vector < int >& cost ) { int m = cost . size (); g = vector < vector < long long >> ( m << 1 , vector < long long > ( m << 1 , inf )); s = source ; t = target ; for ( int i = 0 ; i < g . size (); ++ i ) { g [ i ][ i ] = 0 ; } for ( int i = 0 ; i < m ; ++ i ) { int x = insert ( original [ i ]); int y = insert ( changed [ i ]); g [ x ][ y ] = min ( g [ x ][ y ], static_cast < long long > ( cost [ i ])); } for ( int k = 0 ; k < idx ; ++ k ) { for ( int i = 0 ; i < idx ; ++ i ) { if ( g [ i ][ k ] >= inf ) { continue ; } for ( int j = 0 ; j < idx ; ++ j ) { g [ i ][ j ] = min ( g [ i ][ j ], g [ i ][ k ] + g [ k ][ j ]); } } } f = vector < long long > ( s . length (), - 1 ); long long ans = dfs ( 0 ); return ans >= inf ? - 1 : ans ; } private: int insert ( const string & w ) { Node * node = root ; for ( char c : w ) { int i = c - 'a' ; if ( node -> children [ i ] == nullptr ) { node -> children [ i ] = new Node (); } node = node -> children [ i ]; } if ( node -> v < 0 ) { node -> v = idx ++ ; } return node -> v ; } long long dfs ( int i ) { if ( i >= s . length ()) { return 0 ; } if ( f [ i ] != - 1 ) { return f [ i ]; } long long res = ( s [ i ] == t [ i ]) ? dfs ( i + 1 ) : inf ; Node * p = root ; Node * q = root ; for ( int j = i ; j < s . length (); ++ j ) { p = p -> children [ s [ j ] - 'a' ]; q = q -> children [ t [ j ] - 'a' ]; if ( p == nullptr || q == nullptr ) { break ; } if ( p -> v < 0 || q -> v < 0 ) { continue ; } long long temp = g [ p -> v ][ q -> v ]; if ( temp < inf ) { res = min ( res , temp + dfs ( j + 1 )); } } return f [ i ] = res ; } }; ``` ### Python ```python class Node : __slots__ = [ "children" , "v" ] def __init__ ( self ): self . children : List [ Node | None ] = [ None ] * 26 self . v = - 1 class Solution : def minimumCost ( self , source : str , target : str , original : List [ str ], changed : List [ str ], cost : List [ int ], ) -> int : m = len ( cost ) g = [[ inf ] * ( m << 1 ) for _ in range ( m << 1 )] for i in range ( m << 1 ): g [ i ][ i ] = 0 root = Node () idx = 0 def insert ( w : str ) -> int : node = root for c in w : i = ord ( c ) - ord ( "a" ) if node . children [ i ] is None : node . children [ i ] = Node () node = node . children [ i ] if node . v < 0 : nonlocal idx node . v = idx idx += 1 return node . v @ cache def dfs ( i : int ) -> int : if i >= len ( source ): return 0 res = dfs ( i + 1 ) if source [ i ] == target [ i ] else inf p = q = root for j in range ( i , len ( source )): p = p . children [ ord ( source [ j ]) - ord ( "a" )] q = q . children [ ord ( target [ j ]) - ord ( "a" )] if p is None or q is None : break if p . v < 0 or q . v < 0 : continue res = min ( res , dfs ( j + 1 ) + g [ p . v ][ q . v ]) return res for x , y , z in zip ( original , changed , cost ): x = insert ( x ) y = insert ( y ) g [ x ][ y ] = min ( g [ x ][ y ], z ) for k in range ( idx ): for i in range ( idx ): if g [ i ][ k ] >= inf : continue for j in range ( idx ): # g[i][j] = min(g[i][j], g[i][k] + g[k][j]) if g [ i ][ k ] + g [ k ][ j ] < g [ i ][ j ]: g [ i ][ j ] = g [ i ][ k ] + g [ k ][ j ] ans = dfs ( 0 ) return - 1 if ans >= inf else ans ```