Minimum Cost to Convert String II

Problem Description

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.

Key Insights

• The problem can be modeled as a pathfinding problem where minimum costs are associated with converting substrings.
• A dynamic programming approach can be used to keep track of the minimum cost to convert each prefix of the source string to the corresponding prefix of the target.
• Operations must be disjoint or identical, which adds complexity to how we can combine operations.

Space and Time Complexity

Time Complexity: O(n^2 * m) where n is the length of the source/target strings and m is the length of the original/changed arrays.
Space Complexity: O(n) for the dynamic programming array.

Solution

We will use a dynamic programming approach where we define a DP array dp[i] that represents the minimum cost to convert the first i characters of the source string to the first i characters of the target string.

1. Initialize the DP array with infinity values, except dp[0] which is 0 since no cost is needed to convert an empty string.
2. For each index i in the source string, check all possible substrings that can be converted to the corresponding substrings in the target string.
3. Update the DP array based on the costs given in the cost array for valid conversions.
4. The result will be in dp[n] where n is the length of the string. If dp[n] is still infinity, return -1.

Code Solutions