Minimum Cost to Convert String II — Algorithm Visualization & Coding Challenge

Minimum Cost to Convert String II

Difficulty: Hard
Topics: Graph, DP, Strings

🧩 Problem Statement

You are given two 0-indexed strings source and target, both of length n, consisting of lowercase English characters.

You are also given:

• Two string arrays: original and changed
• An integer array cost

Where:

• cost[i] represents the cost of converting original[i] → changed[i]

🔁 Operation Rules

You start with the string source.

In one operation, you can:

• Pick a substring x
• Convert it to y at cost z
• If there exists an index j such that:
  • original[j] === x
  • changed[j] === y
  • cost[j] === z

You may perform any number of operations, but any pair of operations must satisfy one of the following:

1. Disjoint Substrings

   • Operations on source[a..b] and source[c..d]
   • Valid only if b < c or d < a

2. Same Substring (Repeated Transformation)

   • Operations on source[a..b] and source[c..d]
   • Valid only if a === c AND b === d

🎯 Goal

Return the minimum cost to convert source into target.

If it is impossible, return -1.

⚠️ Note:
Multiple indices may exist such that
original[i] === original[j] and changed[i] === changed[j]

📌 Examples

✅ 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

• Change "b" → "c" at index 1 (cost 5)
• Change "c" → "e" at index 2 (cost 1)
• Change "e" → "b" at index 2 (cost 2)
• Change "d" → "e" at index 3 (cost 20)

Total Cost:
5 + 1 + 2 + 20 = 28

✅ Example 2

Input

source = "abcdefgh"
target = "acdeeghh"
original = ["bcd","fgh","thh"]
changed  = ["cde","thh","ghh"]
cost     = [1,3,5]

Output

9

Explanation

• Convert "bcd" → "cde" (indices 1–3, cost 1)
• Convert "fgh" → "thh" (indices 5–7, cost 3)
• Convert "thh" → "ghh" (same indices, cost 5)

Total Cost:
1 + 3 + 5 = 9

❌ Example 3

Input

source = "abcdefgh"
target = "addddddd"
original = ["bcd","defgh"]
changed  = ["ddd","ddddd"]
cost     = [100,1578]

Output

-1

Explanation It is impossible to convert the string due to overlapping substring constraints.

📏 Constraints

• 1 ≤ source.length = target.length ≤ 1000
• 1 ≤ original.length = changed.length = cost.length ≤ 100
• 1 ≤ original[i].length = changed[i].length ≤ source.length
• All strings contain only lowercase English letters
• original[i] ≠ changed[i]
• 1 ≤ cost[i] ≤ 10^6