Minimum Cost to Convert String I

medium graph floyd-warshall shortest path

Problem

You are given two strings source and target of equal length, plus arrays original, changed, and cost. cost[i] is the price of changing the character original[i] into changed[i]. You may apply any number of such conversions. Return the minimum total cost to turn source into target position by position, or -1 if it is impossible.

Each conversion rule is a weighted directed edge between two of the 26 letters. The cheapest way to turn one letter into another may chain several rules, so we compute the all-pairs cheapest conversion with Floyd-Warshall on a 26 × 26 matrix, then add up dist[source[i]][target[i]] for every position.

Inputsource = "abc", target = "bcd", original = ['a','b','c','a'], changed = ['b','c','d','c'], cost = [1,2,4,10]

Output7

a→b = 1, b→c = 2, c→d = 4. Total 7. (The direct a→c rule costs 10, but a→b→c costs only 3.)

source

target

rules (orig>changed:cost; ...)

def minimum_cost(source, target, original, changed, cost):
    INF = float('inf')
    dist = [[INF] * 26 for _ in range(26)]
    for i in range(26):
        dist[i][i] = 0
    for o, c, w in zip(original, changed, cost):
        u, v = ord(o) - 97, ord(c) - 97
        dist[u][v] = min(dist[u][v], w)
    for k in range(26):
        for i in range(26):
            for j in range(26):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    total = 0
    for a, b in zip(source, target):
        u, v = ord(a) - 97, ord(b) - 97
        if dist[u][v] == INF:
            return -1
        total += dist[u][v]
    return total

function minimumCost(source, target, original, changed, cost) {
  const INF = Infinity;
  const dist = Array.from({ length: 26 }, () => new Array(26).fill(INF));
  for (let i = 0; i < 26; i++) dist[i][i] = 0;
  for (let i = 0; i < original.length; i++) {
    const u = original[i].charCodeAt(0) - 97, v = changed[i].charCodeAt(0) - 97;
    dist[u][v] = Math.min(dist[u][v], cost[i]);
  }
  for (let k = 0; k < 26; k++)
    for (let i = 0; i < 26; i++)
      for (let j = 0; j < 26; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
  let total = 0;
  for (let i = 0; i < source.length; i++) {
    const u = source.charCodeAt(i) - 97, v = target.charCodeAt(i) - 97;
    if (dist[u][v] === INF) return -1;
    total += dist[u][v];
  }
  return total;
}

class Solution {
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        long INF = Long.MAX_VALUE / 4;
        long[][] dist = new long[26][26];
        for (long[] row : dist) Arrays.fill(row, INF);
        for (int i = 0; i < 26; i++) dist[i][i] = 0;
        for (int i = 0; i < original.length; i++) {
            int u = original[i] - 'a', v = changed[i] - 'a';
            dist[u][v] = Math.min(dist[u][v], cost[i]);
        }
        for (int k = 0; k < 26; k++)
            for (int i = 0; i < 26; i++)
                for (int j = 0; j < 26; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        long total = 0;
        for (int i = 0; i < source.length(); i++) {
            int u = source.charAt(i) - 'a', v = target.charAt(i) - 'a';
            if (dist[u][v] >= INF) return -1;
            total += dist[u][v];
        }
        return total;
    }
}

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original,
                          vector<char>& changed, vector<int>& cost) {
        const long long INF = 1e15;
        vector<vector<long long>> dist(26, vector<long long>(26, INF));
        for (int i = 0; i < 26; i++) dist[i][i] = 0;
        for (int i = 0; i < (int) original.size(); i++) {
            int u = original[i] - 'a', v = changed[i] - 'a';
            dist[u][v] = min(dist[u][v], (long long) cost[i]);
        }
        for (int k = 0; k < 26; k++)
            for (int i = 0; i < 26; i++)
                for (int j = 0; j < 26; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        long long total = 0;
        for (int i = 0; i < (int) source.size(); i++) {
            int u = source[i] - 'a', v = target[i] - 'a';
            if (dist[u][v] >= INF) return -1;
            total += dist[u][v];
        }
        return total;
    }
};

Explanation

Picture the 26 letters as nodes. Each rule original[i] → changed[i] with price cost[i] is a directed weighted edge. The cost to turn one letter into another is the cheapest path between them, and applying rules in sequence corresponds to chaining edges — so this is an all-pairs shortest-path problem on a tiny 26-node graph.

We initialise a 26 × 26 matrix to infinity with zeros on the diagonal (a letter converts to itself for free), then drop in each rule, keeping the minimum when two rules share the same pair.

Floyd-Warshall then considers every possible intermediate letter k and asks: is going i → k → j cheaper than the best i → j we know? If so, we update. After looping k over all 26 letters, dist[u][v] holds the cheapest conversion from any letter u to any letter v.

Finally we walk the two strings together. For each position we add dist[source[i]][target[i]]; if any pair is still infinite the conversion is impossible and we return -1.

Worked example: the direct rule a → c costs 10, but Floyd-Warshall discovers a → b → c at cost 3. Summing a→b (1) + b→c (2) + c→d (4) gives the answer 7.

Time: O(26³ + n) Space: O(26²)