🔤 Minimum Cost to Convert String I

Difficulty: Medium
Topic: Graph, Shortest Path

🧩 Problem Statement

You are given two strings:

• source and target
• Both are 0-indexed, have the same length, and contain only lowercase English letters

You are also given:

• original[] → starting characters
• changed[] → resulting characters
• cost[] → cost of conversion

🔄 Allowed Operation

In one operation:

• Pick a character x
• Change it to y
• Pay cost z
• Only allowed if a rule (x → y, cost z) exists

📌 You can apply multiple operations on the same character.

🎯 Objective

Convert source → target with the minimum total cost.

• ✅ Return the minimum cost if possible
• ❌ Return -1 if conversion is impossible

💡 Key Observations

• Direct conversion may not be cheapest
• Characters can be converted using intermediate characters
• Each character position is independent
• This can be modeled as a graph shortest-path problem

📌 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]

Explanation

• b → c costs 5
• c → e costs 1
• e → b costs 2
• d → e costs 20

Total Cost

5 + 1 + 2 + 20 = 28

✅ Output: 28

📌 Example 2

Input

source  = "aaaa"
target  = "bbbb"

original = ["a","c"]
changed  = ["c","b"]
cost     = [1,2]

Explanation

a → c → b
Cost = 1 + 2 = 3 per character
Total = 3 × 4 = 12

✅ Output: 12

📌 Example 3

Input

source  = "abcd"
target  = "abce"

original = ["a"]
changed  = ["e"]
cost     = [10000]

Explanation

• No conversion exists for d → e

❌ Output: -1

🧠 Conceptual Model

• Each character (a–z) is a node
• Each conversion is a directed edge
• Edge weight = conversion cost
• Goal: Find the minimum cost path between characters