Problem

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.

Return the minimum cost to convert the string source to the string target using any 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:

graph LR
	a -->|2| b
	d -->|20| e
	b -->|5| c
	c -->|5| b
	c -->|1| e
	e -->|2| b
  
1
2
3
4
5
6
7
8
9

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 the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 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:

graph LR
	a -->|1| c
	c -->|2| b
  
1
2
3

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.

Example 3:

graph LR
	a -->|10000| e
  
1
2
3

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.

Constraint

  • source, target consist of lowercase English letters.
  • 1 <= cost[i] <= 10^6

Solution

Method 1 - Floyd Warshall Algorithm

To solve this problem, we need to find the minimum cost to convert the source string to the target string by transforming characters according to the given transformation rules defined by original, changed, and cost arrays.

Here’s a step-by-step plan to solve the problem:

  1. Create a Cost Matrix: Create a matrix representing the minimum cost to convert any character to any other character using given transformations. We’ll initialize it with a large value (to represent infinity) and update it based on the given transformations.
  2. Floyd-Warshall Algorithm for All-Pairs Shortest Path: Use the Floyd-Warshall algorithm to find the minimum cost to convert any character to any other character using possibly multiple transformations.
  3. Calculate Total Cost: Iterate through the source and target strings, and use the cost matrix to calculate the total cost of conversion. If any character conversion is not possible, return -1.

Video Explanation

Here is the video explanation of the same:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Solution {

	private static final int INF = Integer.MAX_VALUE; // A large value representing infinity
	public static long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
		int n = source.length();
		int[][] conversionCost = new int[26][26];

		// Initialize conversionCost matrix with INF
		for (int i = 0; i < 26; i++) {
			Arrays.fill(conversionCost[i], INF);
			conversionCost[i][i] = 0; // Cost of changing a character to itself is zero
		}

		// Fill the conversionCost matrix based on the given transformations
		for (int i = 0; i < original.length; i++) {
			int from = original[i] - 'a';
			int to = changed[i] - 'a';
			conversionCost[from][to] = Math.min(conversionCost[from][to], cost[i]);
		}

		// Apply Floyd-Warshall algorithm to find the all-pairs shortest paths
		for (int k = 0; k < 26; k++) {
			for (int i = 0; i < 26; i++) {
				for (int j = 0; j < 26; j++) {
					if (conversionCost[i][k] != INF && conversionCost[k][j] != INF) {
						conversionCost[i][j] = Math.min(conversionCost[i][j], conversionCost[i][k] + conversionCost[k][j]);
					}
				}
			}
		}

		// Calculate the total cost to convert the source to the target
		long totalCost = 0;

		for (int i = 0; i < n; i++) {
			int from = source.charAt(i) - 'a';
			int to = target.charAt(i) - 'a';

			if (conversionCost[from][to] == INF) {
				return -1; // Conversion is not possible
			}

			totalCost += conversionCost[from][to];
		}

		return totalCost;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
    • Floyd Warshall algorithm takes O(m^3) time, where m is number of nodes in graph, and in this problem number of nodes can be 26, as only lower case letters are allowed. So, it O(26^3) = O(1)
    • Calculating the total cost using the distance matrix takes O(n) time
  • 🧺 Space complexity: O(1)
    • The conversionCost matrix takes O(26^2) space, hence O(1)