Minimum Cost to Convert String I

Med

#2656Time: O(M + N + C * (E + V log V)), where N is the length of the strings, M is the length of `original`/`cost` arrays, V is the number of characters (26), E is the number of conversion rules (at most M), and C is the number of unique characters in `source` (at most 26). Since V is a small constant, this simplifies to O(M + N + C * E). In the worst case C=26, so the complexity is dominated by O(M+N) with a larger constant factor for the graph algorithm part.Space: O(V^2 + E), where V is the number of characters (26) and E is the number of conversion rules. V^2 is for the memoization table and E is for the adjacency list. Since V is a constant, this simplifies to O(E).1 company

Algorithms

Shortest Path

Data structures

Array String Graph

Companies

Atlassian

Prompt

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 <= 10⁵
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 10⁶
original[i] != changed[i]

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the character conversions as a directed weighted graph where characters are nodes and conversions are edges. For each required transformation from a character u to v, it runs Dijkstra's algorithm starting from u to find the shortest path (minimum cost) to v. To avoid re-computation, the results of Dijkstra's algorithm are cached.

Algorithm

Create an adjacency list to represent the character conversion graph. The 26 lowercase letters are the nodes.
For each (original[i], changed[i], cost[i]), add a directed edge from original[i] to changed[i] with weight cost[i].
Initialize a minCost[26][26] matrix with a sentinel value (e.g., -1) to cache shortest path costs.
Initialize totalCost = 0.
Iterate through source and target from i = 0 to n-1.
Let u = source.charAt(i) and v = target.charAt(i).
If u == v, continue.
If minCost[u][v] is not yet computed, run Dijkstra's algorithm starting from node u.
- Dijkstra's finds the shortest paths from u to all other nodes.
- Store these computed costs in the minCost[u] row.
After ensuring minCost[u][v] is computed, check its value.
If minCost[u][v] is infinity, it's impossible to convert. Return -1.
Otherwise, add minCost[u][v] to totalCost.
After the loop, return totalCost.

Walkthrough

We first construct a graph where the 26 lowercase letters are the vertices. For each entry in original, changed, and cost, we add a directed edge from original[i] to changed[i] with weight cost[i]. This can be represented using an adjacency list.

We then iterate through the source and target strings. For each index i where source[i] differs from target[i], we need to find the minimum cost to convert source[i] to target[i].

This is a shortest path problem on the graph. We can use Dijkstra's algorithm. To optimize, we can use memoization. We maintain a 2D array, say minCost[26][26], to store the shortest path costs.

When we need the cost from character u to v, we first check our minCost table. If the value is already computed, we use it. If not, we run Dijkstra's algorithm starting from u. This computes the shortest paths from u to all other characters. We store all these results in our minCost table for future use.

The total cost is the sum of these minimum costs for all i. If any required conversion is impossible (no path exists), we return -1.

1import java.util.*;2 3class Solution {4    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {5        List<int[]>[] adj = new ArrayList[26];6        for (int i = 0; i < 26; i++) {7            adj[i] = new ArrayList<>();8        }9        for (int i = 0; i < original.length; i++) {10            adj[original[i] - 'a'].add(new int[]{changed[i] - 'a', cost[i]});11        }12 13        long[][] minCost = new long[26][26];14        for (int i = 0; i < 26; i++) {15            Arrays.fill(minCost[i], -1L);16        }17 18        long totalCost = 0;19        for (int i = 0; i < source.length(); i++) {20            int u = source.charAt(i) - 'a';21            int v = target.charAt(i) - 'a';22 23            if (u == v) {24                continue;25            }26 27            if (minCost[u][v] == -1L) {28                dijkstra(u, adj, minCost[u]);29            }30 31            if (minCost[u][v] == Long.MAX_VALUE) {32                return -1;33            }34            totalCost += minCost[u][v];35        }36 37        return totalCost;38    }39 40    private void dijkstra(int startNode, List<int[]>[] adj, long[] costs) {41        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));42        pq.offer(new long[]{0, startNode});43 44        Arrays.fill(costs, Long.MAX_VALUE);45        costs[startNode] = 0;46 47        while (!pq.isEmpty()) {48            long[] current = pq.poll();49            long currentCost = current[0];50            int u = (int) current[1];51 52            if (currentCost > costs[u]) {53                continue;54            }55 56            for (int[] edge : adj[u]) {57                int v = edge[0];58                int weight = edge[1];59                if (costs[u] != Long.MAX_VALUE && costs[u] + weight < costs[v]) {60                    costs[v] = costs[u] + weight;61                    pq.offer(new long[]{costs[v], v});62                }63            }64        }65    }66}

Complexity

Time

O(M + N + C * (E + V log V)), where N is the length of the strings, M is the length of `original`/`cost` arrays, V is the number of characters (26), E is the number of conversion rules (at most M), and C is the number of unique characters in `source` (at most 26). Since V is a small constant, this simplifies to O(M + N + C * E). In the worst case C=26, so the complexity is dominated by O(M+N) with a larger constant factor for the graph algorithm part.

Space

O(V^2 + E), where V is the number of characters (26) and E is the number of conversion rules. V^2 is for the memoization table and E is for the adjacency list. Since V is a constant, this simplifies to O(E).

Trade-offs

Pros

Conceptually straightforward application of a standard graph algorithm.
It's a 'lazy' approach, only computing shortest paths as they are needed. If the source string only contains a few distinct characters, we run Dijkstra's fewer times.

Cons

Can be less efficient than pre-computing all-pairs shortest paths if many different source characters are present.
The overhead of the priority queue in Dijkstra's can be larger than the simple loops of Floyd-Warshall for a small, dense graph.
The implementation is slightly more complex due to managing the cache and calls to Dijkstra's.

This approach recognizes that the core of the problem is finding the minimum conversion cost between any pair of characters. Since there are only 26 characters (nodes), we can efficiently pre-compute all these minimum costs using the Floyd-Warshall algorithm. After this pre-computation, we can find the cost for each required transformation in constant time.

Algorithm

Create a 2D distance matrix dist[26][26].
Initialize dist[i][i] = 0 and dist[i][j] = infinity for i != j.
Populate dist with direct conversion costs from the input arrays. For each given conversion u -> v with cost c, set dist[u][v] = min(dist[u][v], c).
Run the Floyd-Warshall algorithm on the dist matrix to find all-pairs shortest paths.
- for k from 0 to 25:
- for i from 0 to 25:
- `for j from 0 to 25:`
- `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`
Initialize totalCost = 0.
Iterate through the source and target strings from i = 0 to n-1.
Let u = source.charAt(i) and v = target.charAt(i).
If dist[u][v] is infinity, return -1.
Otherwise, add dist[u][v] to totalCost.
Return totalCost.

Walkthrough

The problem of finding the minimum cost to convert one character to another, possibly through a series of intermediate characters, is equivalent to finding the shortest path in a graph. We can model the 26 lowercase letters as vertices in a directed, weighted graph.

First, we initialize a 2D array, dist[26][26], which will store the shortest path costs. dist[i][j] will hold the minimum cost to convert character i to character j. We initialize dist[i][i] = 0 for all i, and dist[i][j] = infinity for all i != j.

Next, we populate this matrix with the direct conversion costs given. For each (original[k], changed[k], cost[k]), we set dist[original[k]-'a'][changed[k]-'a'] to the minimum of its current value and cost[k].

Then, we apply the Floyd-Warshall algorithm. This algorithm systematically considers every possible intermediate character k for every pair of source i and destination j characters, updating the shortest path dist[i][j] if a shorter path through k is found (dist[i][k] + dist[k][j]).

After running Floyd-Warshall, dist[i][j] contains the true minimum cost for converting character i to j.

Finally, we iterate through the source and target strings. For each position i, if source[i] and target[i] are different, we look up the cost dist[source[i]-'a'][target[i]-'a']. If this cost is infinity, the conversion is impossible, and we return -1. Otherwise, we add the cost to a running total.

The final sum is the minimum total cost.

1import java.util.Arrays;2 3class Solution {4    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {5        long[][] dist = new long[26][26];6        long INF = Long.MAX_VALUE;7 8        for (int i = 0; i < 26; i++) {9            Arrays.fill(dist[i], INF);10            dist[i][i] = 0;11        }12 13        for (int i = 0; i < original.length; i++) {14            int u = original[i] - 'a';15            int v = changed[i] - 'a';16            dist[u][v] = Math.min(dist[u][v], (long)cost[i]);17        }18 19        for (int k = 0; k < 26; k++) {20            for (int i = 0; i < 26; i++) {21                for (int j = 0; j < 26; j++) {22                    if (dist[i][k] != INF && dist[k][j] != INF) {23                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);24                    }25                }26            }27        }28 29        long totalCost = 0;30        for (int i = 0; i < source.length(); i++) {31            int u = source.charAt(i) - 'a';32            int v = target.charAt(i) - 'a';33            if (u == v) {34                continue;35            }36            if (dist[u][v] == INF) {37                return -1;38            }39            totalCost += dist[u][v];40        }41 42        return totalCost;43    }44}

Complexity

Time

O(M + V^3 + N), where N is the length of the strings, M is the length of the `cost` array, and V is the number of characters (26). Since V is a constant, the complexity is dominated by the linear scans, making it O(M + N). The V^3 part is a constant number of operations (26^3 = 17576).

Space

O(V^2) for the distance matrix. Since V=26 is a constant, this is considered O(1) constant space.

Trade-offs

Pros

Very efficient for graphs with a small number of vertices, like this one (26).
The implementation is simple and clean with three nested loops.
Pre-computes all necessary information, making the final cost calculation a fast O(N) loop with constant-time lookups.

Cons

The O(V^3) complexity makes it unsuitable for graphs with a large number of vertices, but that's not a concern here.

Solutions

Solution

1class Solution {2public3  long minimumCost(String source, String target, char[] original,4                   char[] changed, int[] cost) {5    final int inf = 1 << 29;6    int[][] g = new int[26][26];7    for (int i = 0; i < 26; ++i) {8      Arrays.fill(g[i], inf);9      g[i][i] = 0;10    }11    for (int i = 0; i < original.length; ++i) {12      int x = original[i] - 'a';13      int y = changed[i] - 'a';14      int z = cost[i];15      g[x][y] = Math.min(g[x][y], z);16    }17    for (int k = 0; k < 26; ++k) {18      for (int i = 0; i < 26; ++i) {19        for (int j = 0; j < 26; ++j) {20          g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);21        }22      }23    }24    long ans = 0;25    int n = source.length();26    for (int i = 0; i < n; ++i) {27      int x = source.charAt(i) - 'a';28      int y = target.charAt(i) - 'a';29      if (x != y) {30        if (g[x][y] >= inf) {31          return -1;32        }33        ans += g[x][y];34      }35    }36    return ans;37  }38}

1/** * @param {string} source * @param {string} target * @param {character[]} original * @param {character[]} changed * @param {number[]} cost * @return {number} */ var minimumCost =2  function (source, target, original, changed, cost) {3    const [n, m, MAX] = [4      source.length,5      original.length,6      Number.POSITIVE_INFINITY,7    ];8    const g = Array.from({ length: 26 }, () => Array(26).fill(MAX));9    const getIndex = (ch) => ch.charCodeAt(0) - " a ".charCodeAt(0);10    for (let i = 0; i < 26; ++i) g[i][i] = 0;11    for (let i = 0; i < m; ++i) {12      const x = getIndex(original[i]);13      const y = getIndex(changed[i]);14      const z = cost[i];15      g[x][y] = Math.min(g[x][y], z);16    }17    for (let k = 0; k < 26; ++k) {18      for (let i = 0; i < 26; ++i) {19        for (let j = 0; g[i][k] < MAX && j < 26; j++) {20          if (g[k][j] < MAX) {21            g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);22          }23        }24      }25    }26    let ans = 0;27    for (let i = 0; i < n; ++i) {28      const x = getIndex(source[i]);29      const y = getIndex(target[i]);30      if (x === y) continue;31      if (g[x][y] === MAX) return -1;32      ans += g[x][y];33    }34    return ans;35  };

1class Solution {2public:3  long long minimumCost(string source, string target, vector<char> &original,4                        vector<char> &changed, vector<int> &cost) {5    const int inf = 1 << 29;6    int g[26][26];7    for (int i = 0; i < 26; ++i) {8      fill(begin(g[i]), end(g[i]), inf);9      g[i][i] = 0;10    }11    for (int i = 0; i < original.size(); ++i) {12      int x = original[i] - 'a';13      int y = changed[i] - 'a';14      int z = cost[i];15      g[x][y] = min(g[x][y], z);16    }17    for (int k = 0; k < 26; ++k) {18      for (int i = 0; i < 26; ++i) {19        for (int j = 0; j < 26; ++j) {20          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);21        }22      }23    }24    long long ans = 0;25    int n = source.length();26    for (int i = 0; i < n; ++i) {27      int x = source[i] - 'a';28      int y = target[i] - 'a';29      if (x != y) {30        if (g[x][y] >= inf) {31          return -1;32        }33        ans += g[x][y];34      }35    }36    return ans;37  }38};

1class Solution:2    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int], ) -> int: g = [[inf] * 26 for _ in range(26)] for i in range(26): g[i][i] = 0 for x, y, z in zip(original, changed, cost): x = ord(x) - ord('a') y = ord(y) - ord('a') g[x][y] = min(g[x][y], z) for k in range(26): for i in range(26): for j in range(26): g[i][j] = min(g[i][j], g[i][k] + g[k][j]) ans = 0 for a, b in zip(source, target): if a != b: x, y = ord(a) - ord('a'), ord(b) - ord('a') if g[x][y] >= inf: return - 1 ans += g[x][y] return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem