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 hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse 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]; } }; Enter fullscreen mode Exit fullscreen mode 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, 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 Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 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]; }; Enter fullscreen mode Exit fullscreen mode 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.