Algorithms
Medium
2976
3235
Minimum Cost to Convert String I
minimum-cost-to-convert-string-i
"""
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]
"""
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        
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]


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        
```

my_solution = Solution()

test_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] }
assert my_solution.minimumCost(**test_input) == 28

test_input = { "source": "aaaa", "target": "bbbb", "original": ["a","c"], "changed": ["c","b"], "cost": [1,2] }
assert my_solution.minimumCost(**test_input) == 12

test_input = { "source": "abcd", "target": "abce", "original": ["a"], "changed": ["e"], "cost": [10000] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "aaaabadaaa", "target": "dbdadddbad", "original": ["c","a","c","a","a","b","b","b","d","d","c"], "changed": ["a","c","b","d","b","c","a","d","c","b","d"], "cost": [7,8,11,9,7,6,4,6,9,5,9] }
assert my_solution.minimumCost(**test_input) == 56

test_input = { "source": "aaadbdcdac", "target": "cdbabaddba", "original": ["a","c","b","d","b","a","c"], "changed": ["c","a","d","b","c","b","d"], "cost": [7,2,1,3,6,1,7] }
assert my_solution.minimumCost(**test_input) == 39

test_input = { "source": "aababdaacb", "target": "bcdcdcbdcb", "original": ["a","d","d","a","c","b","c","a","c","d","b","b"], "changed": ["b","c","b","d","a","a","b","c","d","a","c","d"], "cost": [11,4,3,2,7,11,7,6,9,2,1,7] }
assert my_solution.minimumCost(**test_input) == 42

test_input = { "source": "aababdbddc", "target": "adcbbbcdba", "original": ["a","d","b","a","d","c","d","b"], "changed": ["b","a","d","c","c","a","b","a"], "cost": [10,6,8,3,6,10,8,6] }
assert my_solution.minimumCost(**test_input) == 72

test_input = { "source": "aabbcabbdb", "target": "acddbabbdd", "original": ["c","d","c","a","d","c","a","d","b","a","b"], "changed": ["d","b","a","c","c","b","b","a","d","d","c"], "cost": [5,3,8,10,9,7,8,7,5,1,10] }
assert my_solution.minimumCost(**test_input) == 32

test_input = { "source": "aabbddccbc", "target": "abbbaabaca", "original": ["a","b","c","b","a","d"], "changed": ["d","c","b","d","b","b"], "cost": [3,8,7,6,7,10] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "aabdbaabaa", "target": "bdaacabcab", "original": ["b","d","d","a","c","c","a","d","a","b"], "changed": ["c","c","b","d","b","d","b","a","c","a"], "cost": [9,1,7,9,2,1,3,8,8,2] }
assert my_solution.minimumCost(**test_input) == 43

test_input = { "source": "aacacaaccd", "target": "dadaacaabd", "original": ["c","c","a","a","d","b","d","d"], "changed": ["b","d","d","b","b","c","c","a"], "cost": [7,8,9,11,4,6,9,10] }
assert my_solution.minimumCost(**test_input) == 77

test_input = { "source": "aacbabbacc", "target": "adbdbcbdaa", "original": ["c","b","a","b","a","c","d","c","d"], "changed": ["b","c","b","d","d","a","b","d","c"], "cost": [2,6,7,4,7,4,3,5,6] }
assert my_solution.minimumCost(**test_input) == 41

test_input = { "source": "aacbbabdad", "target": "ddadcababd", "original": ["d","b","c","a","b","c","d","c","b","a","a"], "changed": ["c","d","d","b","c","b","b","a","a","c","d"], "cost": [7,10,4,2,7,4,4,4,6,2,8] }
assert my_solution.minimumCost(**test_input) == 45

test_input = { "source": "aacbbbbcab", "target": "cdacdcddac", "original": ["b","d","c","c","b","a"], "changed": ["c","c","b","a","a","d"], "cost": [4,7,9,11,3,4] }
assert my_solution.minimumCost(**test_input) == 67

test_input = { "source": "aacbcabcad", "target": "bbcadddcdd", "original": ["b","a","d","a","b","c","a","d","d","b"], "changed": ["d","b","b","d","c","a","c","c","a","a"], "cost": [7,7,9,8,6,3,8,2,1,5] }
assert my_solution.minimumCost(**test_input) == 53

test_input = { "source": "aacbdbcdca", "target": "bbbdbcaacd", "original": ["a","c","b","d","d","a","c","d"], "changed": ["c","b","c","c","b","d","d","a"], "cost": [9,5,4,1,2,4,7,1] }
assert my_solution.minimumCost(**test_input) == 47

test_input = { "source": "aadbbcdbbd", "target": "badddbdbac", "original": ["c","d","c","d","b","a"], "changed": ["b","b","a","a","a","d"], "cost": [11,4,7,8,5,2] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "aadbccbddd", "target": "cacdbabadc", "original": ["d","b","c","d","a","a","c","b"], "changed": ["c","c","b","b","b","d","a","a"], "cost": [5,8,7,2,4,7,1,5] }
assert my_solution.minimumCost(**test_input) == 46

test_input = { "source": "aadbddcabd", "target": "bdcdccbada", "original": ["d","a","a","b","d","b"], "changed": ["b","c","d","c","a","d"], "cost": [6,10,5,8,11,4] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "aaddadccad", "target": "cbaaadbcba", "original": ["c","a","a","d","c","c","b","b","a","d"], "changed": ["a","c","d","c","d","b","d","c","b","b"], "cost": [1,10,2,8,9,1,9,10,5,1] }
assert my_solution.minimumCost(**test_input) == 44

test_input = { "source": "aaddadcdba", "target": "caaaccbbca", "original": ["b","b","c","d","b","c","a","a"], "changed": ["a","d","d","a","c","b","c","b"], "cost": [11,7,10,8,7,5,10,10] }
assert my_solution.minimumCost(**test_input) == 84

test_input = { "source": "abaacbbcaa", "target": "bdbdbcbdcd", "original": ["d","a","d","a","b","b"], "changed": ["a","d","b","b","a","c"], "cost": [10,9,8,11,4,11] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "abacaadcba", "target": "cadbadcdbd", "original": ["b","d","c","a","b","d","b"], "changed": ["a","b","b","b","c","a","d"], "cost": [9,10,6,2,7,10,9] }
assert my_solution.minimumCost(**test_input) == 89

test_input = { "source": "abacbadadc", "target": "aabbdaaccb", "original": ["d","a","b","d","a","a","c","b","c","c","d","b"], "changed": ["c","b","a","a","d","c","b","c","d","a","b","d"], "cost": [2,10,3,6,4,1,5,5,11,4,2,1] }
assert my_solution.minimumCost(**test_input) == 28

test_input = { "source": "abadbbabcd", "target": "cdcbdddcbb", "original": ["d","d","b","a","c","c","c","a"], "changed": ["c","a","a","c","b","d","a","d"], "cost": [2,10,11,7,6,11,7,1] }
assert my_solution.minimumCost(**test_input) == 79

test_input = { "source": "abadcadacc", "target": "cbabaddcba", "original": ["a","d","a","b","c","a","d","b","b","d","c","c"], "changed": ["b","b","d","d","a","c","a","c","a","c","d","b"], "cost": [7,6,11,11,8,10,4,11,2,3,11,7] }
assert my_solution.minimumCost(**test_input) == 60

test_input = { "source": "abadcdadac", "target": "baddbccdac", "original": ["d","c","d","c","b","a"], "changed": ["b","b","c","a","d","d"], "cost": [8,5,9,1,10,2] }
assert my_solution.minimumCost(**test_input) == 57

test_input = { "source": "abbaadacba", "target": "cdbbcadddd", "original": ["d","a","d","c","b","b","c","d","c","a","a"], "changed": ["a","c","c","d","a","d","a","b","b","d","b"], "cost": [8,3,5,8,3,9,3,4,11,4,9] }
assert my_solution.minimumCost(**test_input) == 50

test_input = { "source": "abbaddaacd", "target": "ccbbaccacc", "original": ["d","d","a","b","c","b"], "changed": ["a","c","c","d","b","c"], "cost": [9,8,2,8,3,1] }
assert my_solution.minimumCost(**test_input) == 35

test_input = { "source": "abbbcabddb", "target": "bbccdbbadc", "original": ["c","d","c","a","b","d","d","a","b","b"], "changed": ["d","a","b","c","c","b","c","d","a","d"], "cost": [3,6,9,4,9,6,9,6,10,7] }
assert my_solution.minimumCost(**test_input) == 60

test_input = { "source": "abbbcbabab", "target": "abcacbaddd", "original": ["b","c","a","c","a","d","d","c"], "changed": ["a","b","d","a","b","b","c","d"], "cost": [11,5,8,1,7,7,1,2] }
assert my_solution.minimumCost(**test_input) == 77

test_input = { "source": "abbcaccabb", "target": "ddddddcacc", "original": ["a","b","c","b","a","c","c"], "changed": ["c","c","d","a","d","a","b"], "cost": [2,6,10,11,9,7,3] }
assert my_solution.minimumCost(**test_input) == 82

test_input = { "source": "abbcaccdba", "target": "accadababc", "original": ["d","a","a","c","b","d"], "changed": ["c","d","b","a","a","b"], "cost": [7,4,10,11,5,5] }
assert my_solution.minimumCost(**test_input) == 99

test_input = { "source": "abbdaccada", "target": "acddaccddc", "original": ["b","b","c","a","d","a","d"], "changed": ["a","c","b","b","b","c","c"], "cost": [4,9,3,1,11,3,3] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "abcabdaddb", "target": "dcbadaaacc", "original": ["d","b","a","a","c","c"], "changed": ["c","c","d","b","b","a"], "cost": [3,3,9,3,7,6] }
assert my_solution.minimumCost(**test_input) == 61

test_input = { "source": "abcadcabaa", "target": "bbbdddcaba", "original": ["b","d","c","d","a","c","b","b"], "changed": ["c","b","a","a","c","b","d","a"], "cost": [1,8,4,3,8,3,11,5] }
assert my_solution.minimumCost(**test_input) == 74

test_input = { "source": "abccabacaa", "target": "aaabacbcbb", "original": ["c","c","d","a","d","b","c","b","d","a"], "changed": ["b","a","a","b","b","d","d","a","c","c"], "cost": [9,10,8,6,9,10,2,6,6,8] }
assert my_solution.minimumCost(**test_input) == 57

test_input = { "source": "abdaababbb", "target": "dbdadabadc", "original": ["a","c","c","b","d","a","b"], "changed": ["c","a","b","c","b","b","d"], "cost": [3,4,6,1,8,11,6] }
assert my_solution.minimumCost(**test_input) == 56

test_input = { "source": "abdbaaacaa", "target": "abbbccccad", "original": ["a","a","c","b","d","d","b"], "changed": ["d","b","b","a","a","b","c"], "cost": [3,10,7,2,5,7,3] }
assert my_solution.minimumCost(**test_input) == 49

test_input = { "source": "abdcbdbccc", "target": "dbbcdcabba", "original": ["c","c","d","b","a","c","a","d","b","d","a","b"], "changed": ["d","a","b","d","c","b","b","a","c","c","d","a"], "cost": [9,5,9,6,5,5,5,10,7,7,3,6] }
assert my_solution.minimumCost(**test_input) == 46

test_input = { "source": "acabbbdbdb", "target": "accbccbbab", "original": ["b","d","c","d","b","c"], "changed": ["a","a","a","c","d","d"], "cost": [7,7,10,9,7,1] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "acadadccbb", "target": "dcaaabbbdd", "original": ["a","c","c","a","d","b","b","d","b","a"], "changed": ["d","d","b","b","c","d","a","a","c","c"], "cost": [1,2,1,4,9,4,8,5,11,7] }
assert my_solution.minimumCost(**test_input) == 25

test_input = { "source": "acadbbcdcb", "target": "bcacabdcdd", "original": ["a","b","d","b","b","c","a"], "changed": ["d","c","c","a","d","b","b"], "cost": [3,6,3,10,11,3,6] }
assert my_solution.minimumCost(**test_input) == 61

test_input = { "source": "acaddccaad", "target": "daacadcdda", "original": ["c","c","a","b","b","a","b","d","c","a","d"], "changed": ["a","b","b","d","a","d","c","b","d","c","c"], "cost": [10,8,4,8,3,1,2,8,11,8,6] }
assert my_solution.minimumCost(**test_input) == 52

test_input = { "source": "acbbabcaac", "target": "bdcbaadcab", "original": ["d","c","a","c","b","a","a","b","c","d"], "changed": ["a","a","d","d","c","c","b","a","b","c"], "cost": [9,11,8,6,11,11,1,1,9,9] }
assert my_solution.minimumCost(**test_input) == 45

test_input = { "source": "accabbadbc", "target": "adbbccbcbd", "original": ["a","c","a","d","b","a","c","c","b","b"], "changed": ["c","d","b","c","d","d","b","a","c","a"], "cost": [7,10,9,3,2,5,1,8,11,2] }
assert my_solution.minimumCost(**test_input) == 36

test_input = { "source": "accabbdddd", "target": "cacdccbcad", "original": ["c","a","d","b","d","c","a","b","b","c","d"], "changed": ["d","b","a","d","c","a","d","a","c","b","b"], "cost": [11,6,6,4,7,11,2,7,7,7,2] }
assert my_solution.minimumCost(**test_input) == 51

test_input = { "source": "accbaadbdb", "target": "baccbaacbb", "original": ["b","b","a","d","d","a","c"], "changed": ["a","d","d","b","a","c","a"], "cost": [9,11,6,7,4,2,2] }
assert my_solution.minimumCost(**test_input) == 61

test_input = { "source": "accbddaaab", "target": "baddbaabbd", "original": ["a","b","c","d","d","b","d","b"], "changed": ["b","a","a","b","a","c","c","d"], "cost": [6,3,4,6,1,6,10,6] }
assert my_solution.minimumCost(**test_input) == 57

test_input = { "source": "acccbcdccb", "target": "bdadccdbad", "original": ["a","b","c","c","a","d","d"], "changed": ["b","c","a","d","c","a","c"], "cost": [8,1,1,9,3,10,4] }
assert my_solution.minimumCost(**test_input) == 48

test_input = { "source": "accccbccda", "target": "daadbbcaac", "original": ["a","c","a","a","d","d"], "changed": ["c","d","d","b","b","c"], "cost": [3,6,6,10,9,8] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "acdacbdadb", "target": "aacccbbacd", "original": ["b","b","a","a","d","c"], "changed": ["d","a","b","d","a","a"], "cost": [6,1,9,6,8,11] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "acdbcdadbd", "target": "daaadaaadd", "original": ["c","a","b","b","b","d","a"], "changed": ["d","c","d","c","a","b","d"], "cost": [3,9,4,6,1,9,3] }
assert my_solution.minimumCost(**test_input) == 54

test_input = { "source": "acddadcbca", "target": "ddaabaaaac", "original": ["b","d","c","a","b","d","c","b","d","c","a"], "changed": ["c","a","b","c","d","c","a","a","b","d","d"], "cost": [7,8,2,10,1,7,8,1,1,11,4] }
assert my_solution.minimumCost(**test_input) == 35

test_input = { "source": "adaadcaddd", "target": "cdddbdccad", "original": ["c","c","c","d","b","a","d"], "changed": ["d","a","b","b","d","b","c"], "cost": [10,9,2,2,7,1,10] }
assert my_solution.minimumCost(**test_input) == 92

test_input = { "source": "adaaddacba", "target": "aabbddbbdd", "original": ["c","b","a","b","c","b"], "changed": ["b","c","b","a","d","d"], "cost": [10,7,7,6,8,5] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "adacdcdacd", "target": "ccbabbbbdc", "original": ["a","b","c","a","d","b","a","c"], "changed": ["c","d","d","d","a","c","b","a"], "cost": [4,3,1,1,6,4,10,6] }
assert my_solution.minimumCost(**test_input) == 99

test_input = { "source": "adadbabcdd", "target": "abbcdcbdba", "original": ["c","d","b","a","c","b","a"], "changed": ["d","b","d","b","b","a","c"], "cost": [11,10,6,1,5,3,8] }
assert my_solution.minimumCost(**test_input) == 80

test_input = { "source": "adadcabbda", "target": "cabadddccc", "original": ["c","a","b","b","a","d","d"], "changed": ["b","d","d","c","b","c","b"], "cost": [7,2,8,4,4,4,7] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "adbaabacdc", "target": "bccbbadcdc", "original": ["c","b","b","d","c","a","b"], "changed": ["b","a","c","a","a","d","d"], "cost": [5,2,6,1,7,7,1] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "adbadbaacb", "target": "bccdbdccab", "original": ["d","a","c","b","c","d","a","b","c","b","a","d"], "changed": ["a","c","b","c","a","b","b","d","d","a","d","c"], "cost": [3,7,7,9,2,9,10,2,9,5,11,8] }
assert my_solution.minimumCost(**test_input) == 65

test_input = { "source": "adbcdaddda", "target": "cbdccabcbc", "original": ["c","a","d","d","b","b","b"], "changed": ["a","c","c","a","d","c","a"], "cost": [8,5,5,10,10,3,9] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "adcacaaabb", "target": "daaadadcbb", "original": ["d","b","a","a","d","c","b","b","d","c","c","a"], "changed": ["b","c","d","c","c","a","a","d","a","b","d","b"], "cost": [2,3,2,4,5,9,11,3,10,1,9,2] }
assert my_solution.minimumCost(**test_input) == 31

test_input = { "source": "adcbbbdada", "target": "cdaabadcdc", "original": ["a","a","b","c","d","b","d"], "changed": ["c","d","c","d","a","a","c"], "cost": [11,11,2,8,5,7,5] }
assert my_solution.minimumCost(**test_input) == 60

test_input = { "source": "adccbabbca", "target": "dcdbbdabba", "original": ["a","d","d","b","c","b","a"], "changed": ["c","b","c","c","a","d","d"], "cost": [5,10,10,1,6,7,7] }
assert my_solution.minimumCost(**test_input) == 90

test_input = { "source": "adcdcbacab", "target": "acddaddadc", "original": ["b","d","c","d","c","d","b","c","a","a","a","b"], "changed": ["a","b","b","c","a","a","d","d","c","b","d","c"], "cost": [2,11,11,9,1,3,6,9,6,4,8,5] }
assert my_solution.minimumCost(**test_input) == 47

test_input = { "source": "addbaccbbd", "target": "cabdcdadcc", "original": ["b","d","d","d","c","b","a","c","c"], "changed": ["a","c","a","b","b","d","d","a","d"], "cost": [10,11,5,6,10,1,4,8,8] }
assert my_solution.minimumCost(**test_input) == 82

test_input = { "source": "addbacdaac", "target": "abddcadbcb", "original": ["d","a","c","b","a","c","a","d","c","d","b"], "changed": ["c","c","b","d","d","d","b","b","a","a","c"], "cost": [9,2,9,4,11,6,10,3,7,2,5] }
assert my_solution.minimumCost(**test_input) == 37

test_input = { "source": "addbcccdcb", "target": "cbbdbddacb", "original": ["d","c","a","a","b","b","c"], "changed": ["c","d","b","d","d","c","b"], "cost": [2,6,4,3,7,7,8] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "addcadccaa", "target": "dbbcaccabc", "original": ["a","b","d","b","d","a","c","b","a","c"], "changed": ["c","d","a","c","b","b","d","a","d","a"], "cost": [8,11,5,1,11,4,3,8,11,4] }
assert my_solution.minimumCost(**test_input) == 49

test_input = { "source": "addcdbdadb", "target": "bcabdcccbd", "original": ["b","b","a","c","d","a","b","c","a"], "changed": ["a","c","c","a","a","b","d","b","d"], "cost": [2,4,8,8,3,5,2,7,2] }
assert my_solution.minimumCost(**test_input) == 59

test_input = { "source": "adddbbdbdb", "target": "cdbadcaccc", "original": ["b","c","c","b","a","c","b","a","a","d","d"], "changed": ["d","a","b","a","b","d","c","c","d","a","c"], "cost": [1,1,1,8,6,9,3,6,5,3,10] }
assert my_solution.minimumCost(**test_input) == 40

test_input = { "source": "adddccacca", "target": "cdcdcccdac", "original": ["d","c","a","d","b","b","b","a","d","a","c","c"], "changed": ["c","a","c","a","d","a","c","b","b","d","d","b"], "cost": [7,7,6,10,1,1,11,5,3,2,10,3] }
assert my_solution.minimumCost(**test_input) == 33

test_input = { "source": "baacbbcdaa", "target": "abdbdbbabd", "original": ["c","d","c","b","a","c","b","d","b"], "changed": ["d","c","b","a","d","a","d","a","c"], "cost": [9,5,5,2,9,4,5,3,6] }
assert my_solution.minimumCost(**test_input) == 76

test_input = { "source": "baadcdabbc", "target": "acbccadccd", "original": ["b","b","a","a","a","d","d","d","c","c","b"], "changed": ["c","a","c","b","d","c","a","b","b","d","d"], "cost": [8,6,5,10,11,1,1,6,3,1,4] }
assert my_solution.minimumCost(**test_input) == 37

test_input = { "source": "baadcdabda", "target": "abdbcdaaca", "original": ["b","b","c","d","d","a","c"], "changed": ["d","a","a","b","c","b","d"], "cost": [11,8,7,3,10,4,1] }
assert my_solution.minimumCost(**test_input) == 48

test_input = { "source": "babababdba", "target": "ccdaaabbac", "original": ["c","d","b","a","d","a","b"], "changed": ["b","a","d","c","c","d","c"], "cost": [8,5,6,2,8,6,8] }
assert my_solution.minimumCost(**test_input) == 55

test_input = { "source": "babbacabba", "target": "adacccdcba", "original": ["c","d","d","d","c","b","b","b","a"], "changed": ["a","b","c","a","d","a","c","d","c"], "cost": [1,1,8,3,2,2,11,8,3] }
assert my_solution.minimumCost(**test_input) == 27

test_input = { "source": "babbadbabc", "target": "ccdabbcbba", "original": ["a","c","d","a","b","d","b","b"], "changed": ["b","d","c","d","a","a","c","d"], "cost": [3,3,1,4,4,8,2,9] }
assert my_solution.minimumCost(**test_input) == 46

test_input = { "source": "bacbddaacb", "target": "dcdaaadcda", "original": ["a","d","a","a","d","c","b","c","c","b"], "changed": ["d","c","c","b","b","b","a","a","d","c"], "cost": [8,5,1,10,8,6,2,1,6,8] }
assert my_solution.minimumCost(**test_input) == 46

test_input = { "source": "baccbbcdcb", "target": "cabadbbacc", "original": ["c","a","c","b","c","d","a","b","d","b"], "changed": ["a","b","b","a","d","b","c","d","c","c"], "cost": [4,4,2,11,9,9,1,4,6,1] }
assert my_solution.minimumCost(**test_input) == 24

test_input = { "source": "bacdbbcdba", "target": "cdcdddbbcd", "original": ["d","a","c","b","d","a","b","c","b","c","d"], "changed": ["c","c","a","d","b","b","a","d","c","b","a"], "cost": [3,8,4,6,5,8,6,2,1,6,2] }
assert my_solution.minimumCost(**test_input) == 39

test_input = { "source": "bacdbccabb", "target": "caaccdbaac", "original": ["c","d","d","a","d","c"], "changed": ["d","b","a","b","c","a"], "cost": [8,4,4,4,3,6] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bacddacdba", "target": "bcbbaacdda", "original": ["b","c","c","d","d","b","b","d","a","a","c","a"], "changed": ["a","b","d","b","a","c","d","c","c","d","a","b"], "cost": [5,6,7,4,4,8,8,6,8,3,6,11] }
assert my_solution.minimumCost(**test_input) == 30

test_input = { "source": "badaabbaba", "target": "caadbcadcd", "original": ["b","c","a","c","d","a","b","d","d","b","c"], "changed": ["c","a","d","b","a","c","d","c","b","a","d"], "cost": [4,8,6,3,1,8,3,8,3,6,9] }
assert my_solution.minimumCost(**test_input) == 44

test_input = { "source": "badabbbbac", "target": "dacaabbcaa", "original": ["d","b","a","d","c","b","d","c","a","c","a"], "changed": ["b","c","d","c","a","d","a","d","c","b","b"], "cost": [11,5,9,7,11,11,7,9,6,11,5] }
assert my_solution.minimumCost(**test_input) == 50

test_input = { "source": "badaccbdbd", "target": "dbbdacaaab", "original": ["b","d","b","c","b","d","a","d","a","a","c","c"], "changed": ["d","a","a","a","c","b","d","c","b","c","d","b"], "cost": [3,9,3,11,11,6,2,11,11,2,11,1] }
assert my_solution.minimumCost(**test_input) == 39

test_input = { "source": "badadcccba", "target": "bbdbababcc", "original": ["c","c","a","d","d","d"], "changed": ["a","d","b","a","b","c"], "cost": [1,3,2,2,4,4] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "badbbbccdb", "target": "bbbabbccbd", "original": ["a","c","a","c","d","c","d","b","d","b","a"], "changed": ["c","b","d","d","c","a","b","d","a","c","b"], "cost": [5,4,5,3,4,4,6,3,8,11,4] }
assert my_solution.minimumCost(**test_input) == 30

test_input = { "source": "badcbccabc", "target": "bdcaacbcad", "original": ["d","d","c","d","a","b","c","a"], "changed": ["a","c","d","b","b","a","b","d"], "cost": [1,5,4,5,11,10,8,11] }
assert my_solution.minimumCost(**test_input) == 69

test_input = { "source": "badcbdddcd", "target": "cdcbaddadc", "original": ["c","b","c","d","a","b","b","d","a","c","a","d"], "changed": ["a","c","b","a","c","d","a","b","d","d","b","c"], "cost": [3,2,8,9,11,5,11,11,9,2,8,1] }
assert my_solution.minimumCost(**test_input) == 32

test_input = { "source": "baddbcbdbd", "target": "acdbcadabd", "original": ["a","b","b","c","a","a","b","d","c","d","d"], "changed": ["c","a","d","d","b","d","c","c","b","b","a"], "cost": [9,10,5,4,1,5,7,8,11,9,8] }
assert my_solution.minimumCost(**test_input) == 59

test_input = { "source": "baddbdacad", "target": "cadaccbbab", "original": ["b","a","d","a","c","b","d","c","a","d"], "changed": ["d","b","b","d","a","c","a","b","c","c"], "cost": [3,5,6,7,2,4,4,2,3,9] }
assert my_solution.minimumCost(**test_input) == 32

test_input = { "source": "bbacdcdcda", "target": "cbadabbdcb", "original": ["a","d","b","c","b","c","d","a","d"], "changed": ["b","c","d","a","a","b","b","d","a"], "cost": [11,6,2,8,5,7,5,8,9] }
assert my_solution.minimumCost(**test_input) == 64

test_input = { "source": "bbadbbabbb", "target": "cbaaddaddc", "original": ["d","a","b","c","d","c","b"], "changed": ["b","d","c","b","c","d","d"], "cost": [4,10,1,11,7,1,11] }
assert my_solution.minimumCost(**test_input) == -1

test_input = { "source": "bbadcbcbbc", "target": "aaaccbccbb", "original": ["b","d","b","d","a","c","c","a","b"], "changed": ["c","a","a","b","b","a","b","c","d"], "cost": [8,5,9,4,1,10,1,11,4] }
assert my_solution.minimumCost(**test_input) == 39

test_input = { "source": "bbbadaccbb", "target": "dadcaccadb", "original": ["a","d","d","d","c","b","c","b","c","b"], "changed": ["d","b","c","a","b","d","d","c","a","a"], "cost": [10,1,4,6,4,1,10,3,1,6] }
assert my_solution.minimumCost(**test_input) == 41

test_input = { "source": "bbbadcbadb", "target": "aacbdcddcd", "original": ["a","d","d","c","a","b","c","b"], "changed": ["d","b","a","a","c","c","b","d"], "cost": [3,1,1,9,1,2,1,2] }
assert my_solution.minimumCost(**test_input) == 19

test_input = { "source": "bbbbabbcbc", "target": "adacababac", "original": ["a","c","a","b","b","d","d","a","d","b","c"], "changed": ["d","b","c","c","d","a","b","b","c","a","d"], "cost": [7,9,9,7,3,2,6,8,11,5,8] }
assert my_solution.minimumCost(**test_input) == 39

test_input = { "source": "bbbbdacbcd", "target": "cbadccdaaa", "original": ["d","a","c","b","d","c","a","d","b","a"], "changed": ["c","c","b","c","a","d","d","b","d","b"], "cost": [2,9,11,3,6,11,6,4,5,5] }
assert my_solution.minimumCost(**test_input) == 74