Minimum Cost to Convert String I - Solution & Explanation
Problem Statement
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].
You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.
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 the string "abcd" to string "acbe": - Change value at index 1 from 'b' to 'c' at a cost of 5. - Change value at index 2 from 'c' to 'e' at a cost of 1. - Change value at index 2 from 'e' to 'b' at a cost of 2. - Change value at index 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 = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2] Output: 12 Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.
Example 3:
Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000] Output: -1 Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.
Constraints:
1 <= source.length == target.length <= 105source,targetconsist of lowercase English letters.1 <= cost.length == original.length == changed.length <= 2000original[i],changed[i]are lowercase English letters.1 <= cost[i] <= 106original[i] != changed[i]
Approach Overview
Problem Overview: You are given two strings source and target of equal length and a list of character transformations with associated costs. Each operation converts one character into another. The goal is to compute the minimum total cost to transform source into target. If any position cannot be converted through the given rules, return -1.
Approach 1: Graph Based Shortest Path (O(V * E), Space O(V + E))
Treat each character as a node in a directed weighted graph. Each transformation rule a -> b with cost c becomes an edge. For every character pair needed in the strings, compute the shortest path from the source character to the target character. A simple shortest-path traversal from each starting character accumulates the minimal conversion cost. This works because character conversions may require intermediate steps such as a -> c -> d. The approach models the problem directly as a graph traversal.
Approach 2: Dynamic Programming with Floyd-Warshall (O(26^3), Space O(26^2))
Since the alphabet size is fixed (26 lowercase letters), compute the minimum conversion cost between every pair of characters using the Floyd–Warshall algorithm. Initialize a 26 x 26 matrix with direct transformation costs, then iteratively update using the relation dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). This dynamic programming approach efficiently finds the shortest paths between all pairs of nodes in a shortest path problem. After preprocessing, iterate through the strings and sum the cost for each character conversion.
Approach 3: Graph-based Approach with Dijkstra's Algorithm (O(26 * (E log V)), Space O(V + E))
Build a weighted adjacency list for character transformations and run Dijkstra's algorithm from each character that appears in source. Dijkstra guarantees the optimal path in graphs with non-negative weights. Cache the computed shortest distances so repeated conversions reuse the result. This approach scales well if the transformation rules grow larger and mirrors typical interview solutions for weighted graph problems.
Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path (O(26^3), Space O(26^2))
This is the most direct solution when the node set is small and fixed. Precompute minimal costs between every pair of characters using the Floyd–Warshall all-pairs algorithm. Once the matrix is ready, each string position becomes a constant-time lookup. The overall runtime is dominated by the preprocessing step, which remains effectively constant due to the small alphabet size.
Recommended for interviews: Floyd–Warshall is usually the cleanest answer because the character set is limited to 26 nodes. Interviewers like this observation because it reduces repeated shortest-path searches into a single preprocessing step. Explaining the graph model first shows strong problem understanding, while implementing the Floyd–Warshall optimization demonstrates algorithmic maturity.
Approach 1: Graph Based Shortest Path Approach
In this approach, we can model the problem as a graph where each character is a node, and directed edges with weights indicate a transformation from one character to another. The edges represent 'original to changed' characters with the given cost. To achieve the transformation from source to target, we need to find the minimum cost path for each position in the source string.
We can utilize Dijkstra's algorithm to find the shortest path from each character in source[i] to target[i] based on the transformation rules. For each character transformation, attempt to find the minimum cost path to transform each character accordingly.
dijkstra function is used to find the shortest transformation cost from one character to another. It utilizes a min-heap priority queue to efficiently extract the minimum path cost fascinatingly similar to Dijkstra's algorithm for shortest path in graphs. For each character of the source and target, it calculates the minimum transformation cost.
Code
Python
Complexity
Time Complexity: O(n * (V + E) log V) where V is the number of unique characters (vertices) and E is the number of transformation rules (edges).Space Complexity: O(V + E) for graph representation and auxiliary data structures.
Approach 2: Dynamic Programming with Floyd-Warshall
This approach involves using the Floyd-Warshall algorithm to pre-compute the shortest transformation cost between any two characters. Consider this as an all-pairs shortest path where each character is a node in the graph, and transformations provide weighted edges. First, apply Floyd-Warshall to compute minimum transformation costs between characters. Then, for each character in the source string, find the transformation cost to match the target using pre-computed values.
The Dynamic Programming table dp is filled using the character to character transformation cost. Initial direct transformation costs are added using the problem's input, followed by updates using the Floyd-Warshall algorithm to include indirect transformations for building comprehensive paths.
Code
Python
Complexity
Time Complexity: O(n + V^3), where n is the string length and V is the number of unique characters (26 for lowercase alphabets). Space Complexity: O(V^2) for storing the distance transformation table.
Approach 3: Graph-based Approach with Dijkstra's Algorithm
The primary idea is to use a graph where each letter is a node, and transformations are directed edges with weights (costs). We can use Dijkstra's algorithm to find the shortest path (minimum cost) to convert each character from source to the corresponding character in target.
The Python solution uses the Dijkstra's algorithm to find the minimum cost path between each letter that needs transformation. We maintain a priority queue to efficiently extract the minimum cost transformation at each step.
Complexity
Time Complexity: O(M log C) per pair of letters to transform, where M is the number of edges (transformations) and C is the total graph nodes (the alphabet size). Space Complexity: O(C + M).
Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path
This approach utilizes the Floyd-Warshall algorithm to precompute the minimum cost from every character to every other character. This is helpful as we need to transform multiple characters efficiently.
This Python solution precomputes shortest paths for any character transformation using Floyd-Warshall. We map characters to indices (0 to 25) representing the alphabet.
Complexity
Time Complexity: O(26^3 + N), Space Complexity: O(26^2).
Approach 5: Floyd Algorithm
According to the problem description, we can consider each letter as a node, and the conversion cost between each pair of letters as a directed edge. We first initialize a 26 times 26 two-dimensional array g, where g[i][j] represents the minimum cost of converting letter i to letter j. Initially, g[i][j] = infty, and if i = j, then g[i][j] = 0.
Next, we traverse the arrays original, changed, and cost. For each index i, we update the cost cost[i] of converting original[i] to changed[i] to g[original[i]][changed[i]], taking the minimum value.
Then, we use the Floyd algorithm to calculate the minimum cost between any two nodes in g. Finally, we traverse the strings source and target. If source[i] neq target[i] and g[source[i]][target[i]] geq infty, it means that the conversion cannot be completed, so we return -1. Otherwise, we add g[source[i]][target[i]] to the answer.
After the traversal ends, we return the answer.
The time complexity is O(m + n + |\Sigma|^3), and the space complexity is O(|\Sigma|^2). Where m and n are the lengths of the arrays original and source respectively; and |\Sigma| is the size of the alphabet, that is, |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Graph Based Shortest Path Approach | Time Complexity: O(n * (V + E) log V) where V is the number of unique characters (vertices) and E is the number of transformation rules (edges).Space Complexity: O(V + E) for graph representation and auxiliary data structures. |
| Dynamic Programming with Floyd-Warshall | Time Complexity: O(n + V^3), where n is the string length and V is the number of unique characters (26 for lowercase alphabets). Space Complexity: O(V^2) for storing the distance transformation table. |
| Graph-based Approach with Dijkstra's Algorithm | Time Complexity: O(M log C) per pair of letters to transform, where M is the number of edges (transformations) and C is the total graph nodes (the alphabet size). Space Complexity: O(C + M). |
| Floyd-Warshall Algorithm for All-Pairs Shortest Path | Time Complexity: O(26^3 + N), Space Complexity: O(26^2). |
| Floyd Algorithm | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Based Shortest Path | O(V * E) | O(V + E) | When modeling the problem directly as a graph and computing paths per character |
| Dynamic Programming with Floyd-Warshall | O(26^3) | O(26^2) | Best when the alphabet size is small and fixed |
| Graph + Dijkstra | O(26 * (E log V)) | O(V + E) | Useful when transformation rules form a larger weighted graph |
| Floyd-Warshall All-Pairs Shortest Path | O(26^3) | O(26^2) | Optimal interview solution due to constant alphabet size |
Video Solution
Minimum Cost to Convert String I - Leetcode 2976 - Python • NeetCodeIO • 13,082 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Cost to Convert String I easy or hard?
Minimum Cost to Convert String I Python/Java solution
How to solve Minimum Cost to Convert String I in O(n)?
What is the best approach for Minimum Cost to Convert String I?
Is Minimum Cost to Convert String I asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost to Convert String I?
What is the time complexity of Minimum Cost to Convert String I?
Ready to solve this problem?
Practice Minimum Cost to Convert String I with our built-in code editor and test cases.
Practice on FleetCode