Converting one string into another might seem simple, but when you can swap entire segments using a library of predefined rules and costs, it becomes a fascinating puzzle of optimization. This problem challenges us to find the cheapest path between two strings by breaking them down into manageable, non-overlapping transformations.
Problem Summary
You're given:
- Two main strings,
sourceandtarget, of the same length . - A list of transformation rules:
original[i]can be changed tochanged[i]for a specificcost[i]. - A rule that you can only transform disjoint (non-overlapping) substrings or the exact same substring multiple times.
Your goal:
- Calculate the minimum total cost to turn
sourceintotarget. If it is impossible, return -1.
Examples
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.
Intuition
At its heart, this is a shortest-path problem combined with Dynamic Programming. Because we can change a string to and then to , we first need to find the absolute minimum cost to convert any known substring to any other known substring. This is a classic "all-pairs shortest path" scenario.
-
Map the Strings: We treat each unique string in
originalandchangedas a "node" in a graph. Since strings are hard to index, we give each unique string a numeric ID. - Find Shortest Paths: We use the Floyd-Warshall algorithm. If we know the cost to go from "abc" to "def" and "def" to "ghi", Floyd-Warshall helps us find the cheapest way to go from "abc" to "ghi" directly.
- Dynamic Programming: We define as the minimum cost to convert the suffix of the string starting at index . For each position, we have two choices:
- If
source[i]already matchestarget[i], the cost could be the same as (cost of 0 for this character). Try to match a substring starting at of length that exists in our transformation rules. If we find a valid transformation, the cost is
cost_to_transform+ .Optimization with Hashing: Since checking substrings repeatedly is slow, we use Rolling Hashing to quickly identify if a substring of
sourceortargetmatches one of our known transformation strings.
Walkthrough: Understanding the Examples
Let's look at Example 1: source = "abcd", target = "acbe".
Rules: "a"→"b" (2), "b"→"c" (5), "c"→"b" (5), "c"→"e" (1), "e"→"b" (2), "d"→"e" (20).
- Step 1: Calculate minimum costs between all strings. For example, to get from "c" to "b", we could go "c"→"e"→"b" for a cost of , which is cheaper than the direct "c"→"b" cost of 5.
- Step 2 (DP):
- Index 3: 'd' to 'e'. Cost is 20. .
- Index 2: 'c' to 'b'. Using our shortest path, cost is 3. .
- Index 1: 'b' to 'c'. Cost is 5. .
Index 0: 'a' to 'a'. Cost is 0. .
Result: 28.
Code Blocks
C++ Solution
class Solution {
public:
using ll = long long;
ll minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
unordered_map<string, int> strToId;
int idCount = 0;
// Assign unique IDs to all strings involved in transformations
for (const string& s : original) if (strToId.find(s) == strToId.end()) strToId[s] = idCount++;
for (const string& s : changed) if (strToId.find(s) == strToId.end()) strToId[s] = idCount++;
const ll INF = 1e15;
vector<vector<ll>> dist(idCount, vector<ll>(idCount, INF));
for (int i = 0; i < idCount; i++) dist[i][i] = 0;
// Build the graph
for (int i = 0; i < original.size(); i++) {
int u = strToId[original[i]], v = strToId[changed[i]];
dist[u][v] = min(dist[u][v], (ll)cost[i]);
}
// Floyd-Warshall for all-pairs shortest paths
for (int k = 0; k < idCount; k++) {
for (int i = 0; i < idCount; i++) {
if (dist[i][k] == INF) continue;
for (int j = 0; j < idCount; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int n = source.length();
vector<ll> dp(n + 1, INF);
dp[0] = 0;
// Extract unique lengths of transformation strings to optimize search
set<int> uniqueLens;
for (const string& s : original) uniqueLens.insert(s.length());
for (int i = 0; i < n; i++) {
if (dp[i] == INF) continue;
// Option 1: Characters match
if (source[i] == target[i]) {
dp[i + 1] = min(dp[i + 1], dp[i]);
}
// Option 2: Transform a substring
for (int len : uniqueLens) {
if (i + len > n) continue;
string subS = source.substr(i, len);
string subT = target.substr(i, len);
if (strToId.count(subS) && strToId.count(subT)) {
int u = strToId[subS], v = strToId[subT];
if (dist[u][v] < INF) {
dp[i + len] = min(dp[i + len], dp[i] + dist[u][v]);
}
}
}
}
return dp[n] == INF ? -1 : dp[n];
}
};
Python Solution
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
str_to_id = {}
curr_id = 0
for s in original + changed:
if s not in str_to_id:
str_to_id[s] = curr_id
curr_id += 1
num_nodes = curr_id
inf = float('inf')
dist = [[inf] * num_nodes for _ in range(num_nodes)]
for i in range(num_nodes):
dist[i][i] = 0
for o, c, z in zip(original, changed, cost):
u, v = str_to_id[o], str_to_id[c]
dist[u][v] = min(dist[u][v], z)
# Floyd-Warshall
for k in range(num_nodes):
for i in range(num_nodes):
for j in range(num_nodes):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
n = len(source)
dp = [inf] * (n + 1)
dp[0] = 0
lengths = sorted(list(set(len(s) for s in original)))
for i in range(n):
if dp[i] == inf: continue
if source[i] == target[i]:
dp[i+1] = min(dp[i+1], dp[i])
for length in lengths:
if i + length <= n:
sub_s = source[i:i+length]
sub_t = target[i:i+length]
if sub_s in str_to_id and sub_t in str_to_id:
u, v = str_to_id[sub_s], str_to_id[sub_t]
if dist[u][v] != inf:
dp[i + length] = min(dp[i + length], dp[i] + dist[u][v])
return dp[n] if dp[n] != inf else -1
JavaScript Solution
/**
* @param {string} source
* @param {string} target
* @param {string[]} original
* @param {string[]} changed
* @param {number[]} cost
* @return {number}
*/
var minimumCost = function(source, target, original, changed, cost) {
const strToId = new Map();
let idCount = 0;
for (const s of [...original, ...changed]) {
if (!strToId.has(s)) strToId.set(s, idCount++);
}
const INF = Number.MAX_SAFE_INTEGER;
const dist = Array.from({ length: idCount }, () => Array(idCount).fill(INF));
for (let i = 0; i < idCount; i++) dist[i][i] = 0;
for (let i = 0; i < original.length; i++) {
const u = strToId.get(original[i]);
const v = strToId.get(changed[i]);
dist[u][v] = Math.min(dist[u][v], cost[i]);
}
// Floyd-Warshall
for (let k = 0; k < idCount; k++) {
for (let i = 0; i < idCount; i++) {
for (let j = 0; j < idCount; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
const n = source.length;
const dp = Array(n + 1).fill(INF);
dp[0] = 0;
const uniqueLens = [...new Set(original.map(s => s.length))];
for (let i = 0; i < n; i++) {
if (dp[i] === INF) continue;
if (source[i] === target[i]) {
dp[i+1] = Math.min(dp[i+1], dp[i]);
}
for (const len of uniqueLens) {
if (i + len <= n) {
const subS = source.substring(i, i + len);
const subT = target.substring(i, i + len);
if (strToId.has(subS) && strToId.has(subT)) {
const u = strToId.get(subS);
const v = strToId.get(subT);
if (dist[u][v] < INF) {
dp[i + len] = Math.min(dp[i + len], dp[i] + dist[u][v]);
}
}
}
}
}
return dp[n] === INF ? -1 : dp[n];
};
Key Takeaways
- Graph Reduction: Converting complex string transformations into a graph problem where strings are nodes and costs are edges.
- Floyd-Warshall Algorithm: An efficient way to pre-calculate the shortest path between all possible pairs of nodes, allowing for indirect transformations.
- Linear Dynamic Programming: Breaking the problem into sub-problems (suffixes) to find the global minimum cost through a series of local decisions.
Final Thoughts
This problem is a masterclass in combining multiple algorithmic techniques. In the real world, this logic is used in Data Compression and Diffing Algorithms (like the ones powering Git). Being able to look at a string and see it as a series of graph traversals is a key skill for senior-level technical interviews and high-performance system design.
Top comments (0)