Minimum Cost to Convert String I
Understanding the Problem
We need to convert one string into another, character by character. Each position is independent: the cost at position i depends only on converting source[i] to target[i]. The total cost is the sum of the individual character conversion costs.
Conversions can also be chained. There may be no direct rule from 'c' to 'b', but if 'c' can become 'e' for cost 1 and 'e' can become 'b' for cost 2, then 'c' can become 'b' for cost 3. Finding the cheapest such chain is a shortest path problem.
If we model each of the 26 lowercase letters as a node in a graph and each (original[i], changed[i], cost[i]) triplet as a directed edge, then finding the minimum cost to convert character x to character y is equivalent to finding the shortest path from node x to node y in this graph.
Key Constraints:
original[i], changed[i] are lowercase English letters→ The graph has at most 26 nodes regardless of input size. That makes an O(V^3) all-pairs algorithm cost about 17,576 operations, which is a fixed constant.1 <= source.length <= 10^5→ The string can be long, so the per-position cost lookup must be O(1) after preprocessing the graph once.1 <= cost[i] <= 10^6with up to 10^5 positions → A single path can sum many edges, and the total can reach roughly 10^5 × 26 × 10^6, well beyond a 32-bit integer. The accumulator and the distance matrix must use 64-bit integers.
Approach 1: Dijkstra from Each Source Character
Intuition
For each character that needs converting, the cheapest way to reach the target character is a single-source shortest path, which Dijkstra's algorithm computes.
Running Dijkstra once per string position would repeat work, since many positions share the same source character. There are only 26 possible source characters, so Dijkstra runs at most 26 times, once per starting letter, and the results cover every position. Each conversion then becomes a table lookup.
The plan: build a graph of 26 nodes (one per letter), run Dijkstra from each node, and store the shortest distance to every other node in a 26x26 table.
Algorithm
- Build an adjacency list for the 26-node character graph. For duplicate edges (same source and destination), keep only the minimum cost.
- Run Dijkstra's algorithm from each of the 26 characters to compute shortest paths to all other characters.
- Store results in a 26x26 distance matrix.
- Iterate through the string. For each position
i: - If
source[i] == target[i], add 0 to the total cost. - Otherwise, look up
dist[source[i]][target[i]]. If it's infinity, return -1. Otherwise, add it to the total cost. - Return the total cost.
Visualization and Code
Loading animation...
- Time Complexity: O(26^3 + n) = O(n). Running Dijkstra 26 times on a 26-node graph costs O(26^3) = O(17,576). The string traversal is O(n). Since 26^3 is a constant, the overall complexity is O(n).
- Space Complexity: O(26^2 + n) = O(n). The 26x26 distance matrix is O(1) in terms of input size. The input strings take O(n) space.
The Dijkstra approach runs the algorithm 26 times with separate per-source bookkeeping. The next approach computes all-pairs shortest paths with a single triple-nested loop over the 26 nodes.
Approach 2: Floyd-Warshall (Optimal)
Intuition
With only 26 nodes, Floyd-Warshall computes the shortest path between every pair of characters in a single triple-nested loop. For every pair of nodes (i, j), it checks whether routing through some intermediate node k is cheaper than the best path found so far.
The algorithm considers every node as a possible intermediate. After all 26 intermediates are processed, dist[i][j] holds the cheapest cost to convert character i into character j, whether directly or through a chain of conversions.
Floyd-Warshall fits this problem well: the graph is small, we need all-pairs distances rather than a single source, and the implementation is three nested loops over the 26 characters with no auxiliary data structures.
Floyd-Warshall rests on an inductive invariant. After the loop for intermediate node k finishes, dist[i][j] holds the shortest path from i to j that uses only nodes {0, 1, ..., k} as intermediates. Any shortest path either avoids node k (already captured before this iteration) or passes through it once (captured by dist[i][k] + dist[k][j]). After all 26 nodes have served as intermediate, the matrix holds the true shortest paths.
Algorithm
- Initialize a 26x26 distance matrix with infinity everywhere, except
dist[i][i] = 0for all i. - For each conversion rule
(original[i], changed[i], cost[i]), setdist[original[i]][changed[i]]to the minimum of its current value andcost[i](handling duplicate edges). - Run Floyd-Warshall: for each intermediate node
k(0 to 25), for each pair (i, j), check ifdist[i][k] + dist[k][j] < dist[i][j]. If so, update. - Iterate through the string. For each position where
source[i] != target[i], look up the shortest path cost. If any lookup returns infinity, return -1. Otherwise, sum up all costs.
Visualization and Code
Loading animation...
- Time Complexity: O(26^3 + n) = O(n). Floyd-Warshall on 26 nodes takes O(26^3) = 17,576 operations, which is a constant. Iterating through the string is O(n). The dominant term is O(n).
- Space Complexity: O(26^2 + n) = O(n). The 26x26 distance matrix uses O(676) = O(1) space. The input strings are O(n).