Minimum Cost to Convert String I

Medium
1718.

Minimum Cost to Convert String I

Minimum Cost to Convert String I is a medium coding problem on arrays, strings and graph, asked in Amazon and Google interviews.

You are given two strings source and target of the same length, both of lowercase English letters, and three arrays original, changed and cost of the same length. Each original[i] and changed[i] is a single lowercase letter.

In one operation you may change a character x of the current string into y at a cost of z if there is an index j with original[j] == x, changed[j] == y and cost[j] == z. Operations may be repeated any number of times, on any positions.

Return the minimum total cost of turning source into target, or -1 if it is impossible.

CodeKairo bounds the string length and the costs (see the constraints) so the total always fits in a 32-bit integer.

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
a stays a; b → c costs 5; c → b is cheapest as c → e → b for 1 + 2 = 3; d → e costs 20. Total 5 + 3 + 20 = 28.

Example 2

Input
source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output
12
Explanation
Each a becomes b through c for 1 + 2 = 3; four positions cost 12.

Example 3

Input
source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [1000]
Output
-1
Explanation
No rule ever turns a d into an e.

Constraints

  • 1 <= source.length == target.length <= 10^4
  • source and target consist of lowercase English letters
  • 1 <= cost.length == original.length == changed.length <= 2000
  • original[i] and changed[i] are lowercase English letters
  • 1 <= cost[i] <= 10^3
  • original[i] != changed[i]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} source
 * @param {string} target
 * @param {string[]} original
 * @param {string[]} changed
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(source, target, original, changed, cost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Convert String I — Problem & Solution

Minimum Cost to Convert String I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Cost to Convert String I is a medium coding problem on arrays, strings and graph, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Graph, Shortest Path
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two strings source and target of the same length, both of lowercase English letters, and three arrays original, changed and cost of the same length. Each original[i] and changed[i] is a single lowercase letter.

In one operation you may change a character x of the current string into y at a cost of z if there is an index j with original[j] == x, changed[j] == y and cost[j] == z. Operations may be repeated any number of times, on any positions.

Return the minimum total cost of turning source into target, or -1 if it is impossible.

CodeKairo bounds the string length and the costs (see the constraints) so the total always fits in a 32-bit integer.

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: a stays a; b → c costs 5; c → b is cheapest as c → e → b for 1 + 2 = 3; d → e costs 20. Total 5 + 3 + 20 = 28.

Example 2

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: Each a becomes b through c for 1 + 2 = 3; four positions cost 12.

Example 3

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [1000]
Output: -1
Explanation: No rule ever turns a d into an e.

Constraints

  • 1 <= source.length == target.length <= 10^4
  • source and target consist of lowercase English letters
  • 1 <= cost.length == original.length == changed.length <= 2000
  • original[i] and changed[i] are lowercase English letters
  • 1 <= cost[i] <= 10^3
  • original[i] != changed[i]

Hints for Minimum Cost to Convert String I

  1. Hint 1

    Each position is independent: the total is the sum, over positions, of the cheapest way to turn source[i] into target[i].

  2. Hint 2

    Treat the 26 letters as nodes of a weighted directed graph with an edge original[j] → changed[j] of weight cost[j] (keep the cheapest of parallel rules). The cheapest conversion is a shortest path.

  3. Hint 3

    With only 26 nodes, Floyd–Warshall gives every letter-to-letter cost at once; then sum up, returning -1 as soon as some needed pair is unreachable.

How to solve Minimum Cost to Convert String I

Conversions of different positions never interact, so the problem reduces to the cheapest letter-to-letter conversion — an all-pairs shortest path on a 26-node graph — summed over the positions.

Approach

  1. Initialise dist[x][x] = 0 and dist[x][y] = ∞ otherwise; for each rule set dist[o][c] = min(dist[o][c], cost).
  2. Run Floyd–Warshall over the 26 letters.
  3. For each position i, add dist[source[i]][target[i]]; if it is ∞, return -1.
  4. Return the sum.

Why it works

A sequence of operations applied to one position is a walk in the letter graph from source[i] to target[i] whose cost is the sum of its edge weights, and the cheapest such walk is a shortest path. Positions do not share any resource, so minimising each one separately minimises the total.

Complexity

  • Time — O(26³ + m + n)
  • Space — O(26²)

Pitfalls

  • Several rules can join the same pair of letters with different costs — keep the cheapest.
  • Positions where source[i] == target[i] cost nothing.
  • In the original problem the total can exceed 32 bits; CodeKairo's bounds keep it below 2.5 · 10^8.

Reference solution

Python

from typing import List

def minimumCost(source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
    INF = float("inf")
    d = [[0 if i == j else INF for j in range(26)] for i in range(26)]
    for o, c, w in zip(original, changed, cost):
        a, b = ord(o) - 97, ord(c) - 97
        if w < d[a][b]:
            d[a][b] = w
    for k in range(26):
        dk = d[k]
        for i in range(26):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in range(26):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    total = 0
    for s, t in zip(source, target):
        w = d[ord(s) - 97][ord(t) - 97]
        if w == INF:
            return -1
        total += w
    return total

Java

public static int minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {
    final int INF = 1000000000;
    int[][] d = new int[26][26];
    for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) d[i][j] = i == j ? 0 : INF;
    for (int r = 0; r < original.length; r++) {
        int a = original[r].charAt(0) - 'a', b = changed[r].charAt(0) - 'a';
        d[a][b] = Math.min(d[a][b], cost[r]);
    }
    for (int k = 0; k < 26; k++)
        for (int x = 0; x < 26; x++) {
            if (d[x][k] == INF) continue;
            for (int y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
        }
    long total = 0;
    for (int p = 0; p < source.length(); p++) {
        int w = d[source.charAt(p) - 'a'][target.charAt(p) - 'a'];
        if (w == INF) return -1;
        total += w;
    }
    return (int) total;
}

C++

int minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
    const int INF = 1000000000;
    vector<vector<int>> d(26, vector<int>(26, INF));
    for (int i = 0; i < 26; i++) d[i][i] = 0;
    for (size_t r = 0; r < original.size(); r++) {
        int a = original[r][0] - 'a', b = changed[r][0] - 'a';
        d[a][b] = min(d[a][b], cost[r]);
    }
    for (int k = 0; k < 26; k++)
        for (int x = 0; x < 26; x++) {
            if (d[x][k] == INF) continue;
            for (int y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
        }
    long long total = 0;
    for (size_t p = 0; p < source.size(); p++) {
        int w = d[source[p] - 'a'][target[p] - 'a'];
        if (w == INF) return -1;
        total += w;
    }
    return (int) total;
}

JavaScript

var minimumCost = function(source, target, original, changed, cost) {
    var INF = 1000000000;
    var d = [];
    for (var i = 0; i < 26; i++) { d.push([]); for (var j = 0; j < 26; j++) d[i].push(i === j ? 0 : INF); }
    for (var r = 0; r < original.length; r++) {
        var a = original[r].charCodeAt(0) - 97, b = changed[r].charCodeAt(0) - 97;
        if (cost[r] < d[a][b]) d[a][b] = cost[r];
    }
    for (var k = 0; k < 26; k++)
        for (var x = 0; x < 26; x++) {
            if (d[x][k] === INF) continue;
            for (var y = 0; y < 26; y++) if (d[x][k] + d[k][y] < d[x][y]) d[x][y] = d[x][k] + d[k][y];
        }
    var total = 0;
    for (var p = 0; p < source.length; p++) {
        var w = d[source.charCodeAt(p) - 97][target.charCodeAt(p) - 97];
        if (w === INF) return -1;
        total += w;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings