> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Cost to Convert String I

> Tested Python solution for LeetCode 2976 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 2976, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [String](/catalog/topics/string), [Graph Theory](/catalog/topics/graph-theory), [Shortest Path](/catalog/topics/shortest-path). [View on LeetCode](https://leetcode.com/problems/minimum-cost-to-convert-string-i/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2976   # by problem number
lcpy gen -s minimum_cost_to_convert_string_i   # by problem name
```

## 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]`.

### Examples

```
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.
```

```
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.
```

```
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^5
* 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^6
* original\[i] != changed\[i]

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_convert_string_i/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_convert_string_i/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(cost.length + 26^3 + n)
    # Space: O(26^2)
    def minimum_cost(
        self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]
    ) -> int:
        unreach = 10**18
        dist = [[unreach] * 26 for _ in range(26)]
        for i in range(26):
            dist[i][i] = 0
        for o, c, w in zip(original, changed, cost, strict=True):
            dist[ord(o) - 97][ord(c) - 97] = min(dist[ord(o) - 97][ord(c) - 97], w)
        for k in range(26):
            dist_k = dist[k]
            for i in range(26):
                dist_ik = dist[i][k]
                if dist_ik == unreach:
                    continue
                dist_i = dist[i]
                for j in range(26):
                    if dist_ik + dist_k[j] < dist_i[j]:
                        dist_i[j] = dist_ik + dist_k[j]
        total = 0
        for s, t in zip(source, target, strict=True):
            d = dist[ord(s) - 97][ord(t) - 97]
            if d == unreach:
                return -1
            total += d
        return total
```

## Complexity

| Time | Space |
| - | - |
| O(cost.length + 26^3 + n) | O(26^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.