Tools: 🧬 Beginner-Friendly Guide 'Minimum Cost to Convert String II' - Problem 2977 (C++, Python, JavaScript)

Problem Summary ## Intuition ## Walkthrough: Understanding the Examples ## Code Blocks ## C++ Solution ## Python Solution ## JavaScript Solution ## Key Takeaways ## Final Thoughts 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. 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: 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: 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. 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. 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 source or target matches one of our known transformation strings. 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). Index 0: 'a' to 'a'. Cost is 0. . 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. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to ? It will become hidden in your post, but will still be visible via the comment's permalink. as well , this person and/or COMMAND_BLOCK: 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]; } }; COMMAND_BLOCK: 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]; } }; COMMAND_BLOCK: 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]; } }; COMMAND_BLOCK: class Solution: def minimumCost(self, 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 COMMAND_BLOCK: class Solution: def minimumCost(self, 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 COMMAND_BLOCK: class Solution: def minimumCost(self, 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 COMMAND_BLOCK: /** * @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]; }; COMMAND_BLOCK: /** * @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]; }; COMMAND_BLOCK: /** * @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]; }; - Two main strings, source and target, of the same length . - A list of transformation rules: original[i] can be changed to changed[i] for a specific cost[i]. - A rule that you can only transform disjoint (non-overlapping) substrings or the exact same substring multiple times. - Calculate the minimum total cost to turn source into target. If it is impossible, return -1. - 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. - 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. - Map the Strings: We treat each unique string in original and changed as 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 matches target[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 source or target matches one of our known transformation strings. - 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. - 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.