Minimum Cost to Convert String II
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given two 0-indexed strings source and target, both of length
n and consisting of lowercase English characters. You are also given two
0-indexed string arrays original and changed, and an integer array
cost, where cost[i] represents the cost of converting the string
original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a
substring x from the string, and change it to y at a cost of z
if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
- The substrings picked in the operations are
source[a..b]andsource[c..d]with eitherb < cord < a. In other words, the indices picked in both operations are disjoint. - The substrings picked in the operations are
source[a..b]andsource[c..d]witha == candb == d. In other words, the indices picked in both operations are identical.
Return _theminimum cost to convert the string _source to the stringtarget usingany 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
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 "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..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 = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.
Example 3
Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
Constraints
1 <= source.length == target.length <= 1000source,targetconsist only of lowercase English characters.1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i],changed[i]consist only of lowercase English characters.original[i] != changed[i]1 <= cost[i] <= 10^6
Solution
Method 1 – Dijkstra's Algorithm with Trie Optimization
Intuition
We want to convert source to target using the minimum cost, where each operation can replace any substring with another at a given cost. This is similar to finding the shortest path in a graph, where each node is a string and edges are substring replacements. To efficiently find applicable substring replacements, we use a Trie to match substrings in source.
Approach
- Build a Trie for all
originalstrings, storing their indices for cost lookup. - Use Dijkstra's algorithm:
- Each state is a string and its current cost.
- Use a min-heap to always expand the lowest-cost state.
- For each position in the current string, use the Trie to find all possible substring replacements.
- For each match, replace the substring, add the cost, and push the new string to the heap if it hasn't been visited with a lower cost.
- Stop when the current string equals
target. - If not possible, return -1.
Code
C++
class Trie {
public:
struct Node {
unordered_map<char, Node*> nxt;
vector<int> idxs;
} root;
void insert(const string& s, int idx) {
Node* cur = &root;
for (char c : s) {
if (!cur->nxt.count(c)) cur->nxt[c] = new Node();
cur = cur->nxt[c];
}
cur->idxs.push_back(idx);
}
vector<pair<int,int>> find(const string& s, int pos) {
vector<pair<int,int>> res;
Node* cur = &root;
for (int i = pos; i < s.size(); ++i) {
if (!cur->nxt.count(s[i])) break;
cur = cur->nxt[s[i]];
for (int idx : cur->idxs) res.push_back({i, idx});
}
return res;
}
};
class Solution {
public:
int minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
if (source == target) return 0;
int n = source.size();
Trie trie;
for (int i = 0; i < original.size(); ++i) trie.insert(original[i], i);
unordered_map<string, int> dist;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [c, s] = pq.top(); pq.pop();
if (c > dist[s]) continue;
if (s == target) return c;
for (int i = 0; i < n; ++i) {
for (auto [j, idx] : trie.find(s, i)) {
string ns = s.substr(0, i) + changed[idx] + s.substr(j+1);
int nc = c + cost[idx];
if (!dist.count(ns) || nc < dist[ns]) {
dist[ns] = nc;
pq.push({nc, ns});
}
}
}
}
return -1;
}
};
Go
// Trie omitted for brevity, use map for substring matching
func minimumCost(source, target string, original, changed []string, cost []int) int {
if source == target { return 0 }
n := len(source)
type state struct{ s string; c int }
dist := map[string]int{source: 0}
pq := &heapMin{}; heap.Init(pq)
heap.Push(pq, node{0, source})
for pq.Len() > 0 {
cur := heap.Pop(pq).(node)
if cur.c > dist[cur.s] { continue }
if cur.s == target { return cur.c }
for i := 0; i < n; i++ {
for idx, o := range original {
if i+len(o) <= n && cur.s[i:i+len(o)] == o {
ns := cur.s[:i] + changed[idx] + cur.s[i+len(o):]
nc := cur.c + cost[idx]
if d, ok := dist[ns]; !ok || nc < d {
dist[ns] = nc
heap.Push(pq, node{nc, ns})
}
}
}
}
}
return -1
}
Java
class Solution {
public int minimumCost(String source, String target, List<String> original, List<String> changed, List<Integer> cost) {
if (source.equals(target)) return 0;
int n = source.length();
Map<String, Integer> dist = new HashMap<>();
dist.put(source, 0);
PriorityQueue<Pair<Integer, String>> pq = new PriorityQueue<>(Comparator.comparingInt(a->a.getKey()));
pq.offer(new Pair<>(0, source));
while (!pq.isEmpty()) {
Pair<Integer, String> cur = pq.poll();
int c = cur.getKey(); String s = cur.getValue();
if (c > dist.get(s)) continue;
if (s.equals(target)) return c;
for (int i = 0; i < n; ++i) {
for (int idx = 0; idx < original.size(); ++idx) {
String o = original.get(idx);
if (i + o.length() <= n && s.substring(i, i + o.length()).equals(o)) {
String ns = s.substring(0, i) + changed.get(idx) + s.substring(i + o.length());
int nc = c + cost.get(idx);
if (!dist.containsKey(ns) || nc < dist.get(ns)) {
dist.put(ns, nc);
pq.offer(new Pair<>(nc, ns));
}
}
}
}
}
return -1;
}
}
Kotlin
class Solution {
fun minimumCost(source: String, target: String, original: List<String>, changed: List<String>, cost: List<Int>): Int {
if (source == target) return 0
val n = source.length
val dist = mutableMapOf<String, Int>()
dist[source] = 0
val pq = PriorityQueue(compareBy<Pair<Int, String>> { it.first })
pq.add(Pair(0, source))
while (pq.isNotEmpty()) {
val (c, s) = pq.poll()
if (c > dist[s]!!) continue
if (s == target) return c
for (i in 0 until n) {
for (idx in original.indices) {
val o = original[idx]
if (i + o.length <= n && s.substring(i, i + o.length) == o) {
val ns = s.substring(0, i) + changed[idx] + s.substring(i + o.length)
val nc = c + cost[idx]
if (dist[ns] == null || nc < dist[ns]!!) {
dist[ns] = nc
pq.add(Pair(nc, ns))
}
}
}
}
}
return -1
}
}
Python
class Solution:
def minimumCost(self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]) -> int:
import heapq
if source == target:
return 0
n = len(source)
dist: dict[str, int] = {source: 0}
pq: list[tuple[int, str]] = [(0, source)]
while pq:
c, s = heapq.heappop(pq)
if c > dist[s]: continue
if s == target: return c
for i in range(n):
for idx, o in enumerate(original):
if i + len(o) <= n and s[i:i+len(o)] == o:
ns = s[:i] + changed[idx] + s[i+len(o):]
nc = c + cost[idx]
if ns not in dist or nc < dist[ns]:
dist[ns] = nc
heapq.heappush(pq, (nc, ns))
return -1
Rust
impl Solution {
pub fn minimum_cost(source: String, target: String, original: Vec<String>, changed: Vec<String>, cost: Vec<i32>) -> i32 {
use std::collections::{BinaryHeap, HashMap};
if source == target { return 0; }
let n = source.len();
let mut dist = HashMap::new();
dist.insert(source.clone(), 0);
let mut pq = BinaryHeap::new();
pq.push(std::cmp::Reverse((0, source.clone())));
while let Some(std::cmp::Reverse((c, s))) = pq.pop() {
if let Some(&d) = dist.get(&s) { if c > d { continue; } }
if s == target { return c; }
for i in 0..n {
for (idx, o) in original.iter().enumerate() {
if i + o.len() <= n && &s[i..i+o.len()] == o {
let ns = format!("{}{}{}", &s[..i], changed[idx], &s[i+o.len()..]);
let nc = c + cost[idx];
if !dist.contains_key(&ns) || nc < dist[&ns] {
dist.insert(ns.clone(), nc);
pq.push(std::cmp::Reverse((nc, ns)));
}
}
}
}
}
-1
}
}
TypeScript
class Solution {
minimumCost(source: string, target: string, original: string[], changed: string[], cost: number[]): number {
if (source === target) return 0;
const n = source.length;
const dist: Record<string, number> = { [source]: 0 };
const pq: [number, string][] = [[0, source]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [c, s] = pq.shift()!;
if (c > dist[s]) continue;
if (s === target) return c;
for (let i = 0; i < n; ++i) {
for (let idx = 0; idx < original.length; ++idx) {
const o = original[idx];
if (i + o.length <= n && s.slice(i, i + o.length) === o) {
const ns = s.slice(0, i) + changed[idx] + s.slice(i + o.length);
const nc = c + cost[idx];
if (!(ns in dist) || nc < dist[ns]) {
dist[ns] = nc;
pq.push([nc, ns]);
}
}
}
}
}
return -1;
}
}
Complexity
- ⏰ Time complexity:
O(L * M * N log K)where L is the length of the string, M is the number of rules, N is the average length of original[i], and K is the number of unique strings visited. - 🧺 Space complexity:
O(K)for the heap and visited map.