Scale Engineer

Minimum Cost to Convert String II

Hard
#2657Time: 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)).1 company
Patterns
Dynamic Programming
Algorithms
Shortest Path
Data structures
ArrayStringTrieGraph
Companies
Atlassian

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

class Solution {    public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {        // Step 1: Pre-computation with Floyd-Warshall        Map<String, Integer> 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];    }}

Complexity

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)).

Trade-offs

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.

Solutions

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 ; } }

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.

← Previous

Previous problem

Next →

Next problem