# Minimum Cost to Convert String I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-to-convert-string-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-convert-string-i
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, String, Graph
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
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 <= 105`
* `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] <= 106`
* `original[i] != changed[i]`

# Approaches
## Repeated Single-Source Shortest Path (Dijkstra)
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.
**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).
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        List<int[]>[] adj = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < original.length; i++) {
            adj[original[i] - 'a'].add(new int[]{changed[i] - 'a', cost[i]});
        }

        long[][] minCost = new long[26][26];
        for (int i = 0; i < 26; i++) {
            Arrays.fill(minCost[i], -1L);
        }

        long totalCost = 0;
        for (int i = 0; i < source.length(); i++) {
            int u = source.charAt(i) - 'a';
            int v = target.charAt(i) - 'a';

            if (u == v) {
                continue;
            }

            if (minCost[u][v] == -1L) {
                dijkstra(u, adj, minCost[u]);
            }

            if (minCost[u][v] == Long.MAX_VALUE) {
                return -1;
            }
            totalCost += minCost[u][v];
        }

        return totalCost;
    }

    private void dijkstra(int startNode, List<int[]>[] adj, long[] costs) {
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, startNode});

        Arrays.fill(costs, Long.MAX_VALUE);
        costs[startNode] = 0;

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentCost = current[0];
            int u = (int) current[1];

            if (currentCost > costs[u]) {
                continue;
            }

            for (int[] edge : adj[u]) {
                int v = edge[0];
                int weight = edge[1];
                if (costs[u] != Long.MAX_VALUE && costs[u] + weight < costs[v]) {
                    costs[v] = costs[u] + weight;
                    pq.offer(new long[]{costs[v], v});
                }
            }
        }
    }
}
```
### 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`.

## All-Pairs Shortest Path (Floyd-Warshall)
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        long[][] dist = new long[26][26];
        long INF = Long.MAX_VALUE;

        for (int i = 0; i < 26; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int i = 0; i < original.length; i++) {
            int u = original[i] - 'a';
            int v = changed[i] - 'a';
            dist[u][v] = Math.min(dist[u][v], (long)cost[i]);
        }

        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        long totalCost = 0;
        for (int i = 0; i < source.length(); i++) {
            int u = source.charAt(i) - 'a';
            int v = target.charAt(i) - 'a';
            if (u == v) {
                continue;
            }
            if (dist[u][v] == INF) {
                return -1;
            }
            totalCost += dist[u][v];
        }

        return totalCost;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  long minimumCost(String source, String target, char[] original,
                   char[] changed, int[] cost) {
    final int inf = 1 << 29;
    int[][] g = new int[26][26];
    for (int i = 0; i < 26; ++i) {
      Arrays.fill(g[i], inf);
      g[i][i] = 0;
    }
    for (int i = 0; i < original.length; ++i) {
      int x = original[i] - 'a';
      int y = changed[i] - 'a';
      int z = cost[i];
      g[x][y] = Math.min(g[x][y], z);
    }
    for (int k = 0; k < 26; ++k) {
      for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
          g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }
    long ans = 0;
    int n = source.length();
    for (int i = 0; i < n; ++i) {
      int x = source.charAt(i) - 'a';
      int y = target.charAt(i) - 'a';
      if (x != y) {
        if (g[x][y] >= inf) {
          return -1;
        }
        ans += g[x][y];
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} source * @param {string} target * @param {character[]} original * @param {character[]} changed * @param {number[]} cost * @return {number} */ var minimumCost =
  function (source, target, original, changed, cost) {
    const [n, m, MAX] = [
      source.length,
      original.length,
      Number.POSITIVE_INFINITY,
    ];
    const g = Array.from({ length: 26 }, () => Array(26).fill(MAX));
    const getIndex = (ch) => ch.charCodeAt(0) - " a ".charCodeAt(0);
    for (let i = 0; i < 26; ++i) g[i][i] = 0;
    for (let i = 0; i < m; ++i) {
      const x = getIndex(original[i]);
      const y = getIndex(changed[i]);
      const z = cost[i];
      g[x][y] = Math.min(g[x][y], z);
    }
    for (let k = 0; k < 26; ++k) {
      for (let i = 0; i < 26; ++i) {
        for (let j = 0; g[i][k] < MAX && j < 26; j++) {
          if (g[k][j] < MAX) {
            g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
          }
        }
      }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
      const x = getIndex(source[i]);
      const y = getIndex(target[i]);
      if (x === y) continue;
      if (g[x][y] === MAX) return -1;
      ans += g[x][y];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  long long minimumCost(string source, string target, vector<char> &original,
                        vector<char> &changed, vector<int> &cost) {
    const int inf = 1 << 29;
    int g[26][26];
    for (int i = 0; i < 26; ++i) {
      fill(begin(g[i]), end(g[i]), inf);
      g[i][i] = 0;
    }
    for (int i = 0; i < original.size(); ++i) {
      int x = original[i] - 'a';
      int y = changed[i] - 'a';
      int z = cost[i];
      g[x][y] = min(g[x][y], z);
    }
    for (int k = 0; k < 26; ++k) {
      for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }
    long long ans = 0;
    int n = source.length();
    for (int i = 0; i < n; ++i) {
      int x = source[i] - 'a';
      int y = target[i] - 'a';
      if (x != y) {
        if (g[x][y] >= inf) {
          return -1;
        }
        ans += g[x][y];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```