2976. Minimum Cost to Convert String I


Problem Description

You have two strings, source and target, which are both of the same length n and consist of lowercase English letters. Additionally, you're provided with two character arrays, original and changed, as well as an integer array cost. Each element in these arrays represents a potential character transformation from original[i] to changed[i] at the given cost[i].

Your task is to transform the source string into the target string. For each character in source that needs to be changed, you can change it into another character using one of the transformations given in the original, changed, and cost arrays. The goal is to achieve this transformation at the minimum total cost. If no sequence of transformations can convert source to target, you should return -1.

Remember that multiple entries in original and changed can represent the same character transformation but might have different costs. You always want to choose the least expensive option for every single character change.

Intuition

To solve this problem, we need to find the cheapest possible transformation for each character in the source string to match the target string. Since each character in source can be independently changed to any other character, this scenario is similar to finding the shortest paths in a graph, where characters are nodes and transformations are directed edges with weights equal to their costs.

For such graph problems, the Floyd-Warshall algorithm is a well-known algorithm that finds the shortest paths between all pairs of nodes in a graph, which fits our needs perfectly. By treating each of the 26 lowercase English letters as a node, we can use the algorithm to find the minimum cost to convert any letter to any other letter after considering all possible intermediate transformations.

The given solution initializes a graph of the transformations and their costs and then applies the Floyd-Warshall algorithm to this graph. After this step, the graph contains the minimum cost for changing any letter to any other directly or through a sequence of transformations.

When we iterate over the source and target strings, we check the cost of transforming each character in source to the corresponding character in target using the previously computed graph. If a transformation is impossible (signified by the cost being inf), we return -1. Otherwise, we keep a running total of the costs for each transformation. By the end of this process, we've calculated the minimum possible cost to transform the source string into the target string.

Learn more about Graph and Shortest Path patterns.

Solution Approach

The solution employs the Floyd-Warshall algorithm, which is an all-pairs shortest path algorithm, and is particularly well-suited for solving problems like our current one where we need the lowest cost to change any character into any other character. This algorithm works even if there are indirect ways of obtaining a transformation at a smaller cost through a sequence of intermediate character changes.

Here's a detailed step-by-step breakdown of the solution implementation:

  1. Graph Initialization: We initialize a 2D array g with dimensions 26 x 26 to represent a graph, where the i-th row and j-th column represent the cost of transforming the i-th letter of the alphabet to the j-th letter. The array is initialized to inf to denote an initially infinite cost between any two characters. The diagonal is set to 0 since the cost of changing a letter to itself is 0.

  2. Graph Construction: We iterate through the original, changed, and cost arrays simultaneously to fill in the graph with given transformation costs. When we encounter duplicate transformations, we keep the one with the lowest cost by using min(g[x][y], z).

  3. Applying the Floyd-Warshall Algorithm: We run a triple nested loop (k, i, j) over all possible characters to find the shortest paths. This part updates the g array such that g[i][j] will contain the minimum cost of converting the letter i to letter j, possibly through an intermediate letter k. After Floyd-Warshall, g will reflect the cheapest cost of direct and indirect character transformations.

  4. Transformation Cost Calculation: We iterate over both source and target at the same time and for each pair (a, b) of characters, we check if they need to be transformed (a != b). If they do, we retrieve the transformation cost from g. If g indicates an inf cost, this means no transformation is available and we return -1. Otherwise, we accumulate the cost of each transformation to calculate the total cost.

  5. Returning the Result: Finally, if all characters have been successfully transformed or no transformation was needed, we return the accumulated cost.

In summary, this solution leverages a dynamic programming approach to comprehensively calculate the cheapest transformations between all possible pairs of characters using the Floyd-Warshall algorithm and then uses that information to determine the minimum cost of transforming source to target.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Let's illustrate the solution approach using a simple example:

Suppose source = "abc", target = "xyz", and we have the following arrays of transformations:

  • original = ['a', 'b', 'c', 'b']
  • changed = ['x', 'y', 'x', 'z']
  • cost = [5, 10, 7, 3]

This indicates that we can transform 'a' to 'x' at a cost of 5, 'b' to 'y' at a cost of 10, 'c' to 'x' at a cost of 7, and 'b' to 'z' at a cost of 3.

Following the steps of the solution approach:

  1. Graph Initialization: We create a 2D array g with dimensions 26 x 26, representing the graph with all nodes initialized to inf, except the diagonal which is initialized to 0 since transforming a letter to itself has no cost.

  2. Graph Construction: We iterate through our transformation arrays and update g with the given costs. After iterating, g looks like this (partial view):

    1(to)
    2 a   b   c   x   y   z
    3a 0  inf inf inf inf inf
    4b inf   0 inf inf  10   3
    5c inf inf   0   7 inf inf
    6x inf inf inf   0 inf inf
    7...
    8(from)

    Since we have two transformations for 'b' (to 'y' and 'z'), we keep the cheaper one: 'b' to 'z' at a cost of 3.

  3. Applying the Floyd-Warshall Algorithm: We run the Floyd-Warshall algorithm, and in this small example no new paths would be found since there are no intermediate nodes that provide a shorter path. After applying the algorithm, the g array would remain unchanged.

  4. Transformation Cost Calculation: We simultaneously iterate over source and target. For each character in source, we check the corresponding cost to transform it into the target character:

    • Transforming 'a' to 'x': Direct cost is 5.
    • Transforming 'b' to 'y': Since we kept the cost of 'b' to 'z' as 3 in step 2 (ignoring the cost of 10), we need to check if there's an indirect way to get from 'b' to 'y'. Since our example has no intermediate transformations that enable 'b' to 'y', we would have to consider the direct cost of 10.
    • Transforming 'c' to 'z': No direct transformation exists. If g[c][z] is still inf, this means it's not possible to transform 'c' to 'z', and we should return -1.

    In our example, transforming 'c' to 'z' directly is impossible, so we would check g[c][z]. If it's inf, then the total cost is -1 as the transformation cannot be completed. Assuming it's possible through other transformations, we would sum the costs from g.

  5. Returning the Result: If the transformation of 'c' to 'z' is impossible, we return -1. Otherwise, we would return the sum of the valid transformation costs, which in our case is 5 + 10 + (cost of c to z) if g[c][z] is not inf.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minimum_cost(
6        self,
7        source: str,
8        target: str,
9        original: List[str],
10        changed: List[str],
11        cost: List[int]
12    ) -> int:
13        # Create a 26x26 graph representing potential cost from one character to another
14        graph = [[inf] * 26 for _ in range(26)]
15      
16        # Set the cost of converting a character to itself as 0
17        for i in range(26):
18            graph[i][i] = 0
19      
20        # Fill in the graph with the given cost for each direct transformation.
21        # If there are multiple transformations, take the minimum cost.
22        for original_char, changed_char, current_cost in zip(original, changed, cost):
23            x = ord(original_char) - ord('a')
24            y = ord(changed_char) - ord('a')
25            graph[x][y] = min(graph[x][y], current_cost)
26      
27        # Use Floyd-Warshall algorithm to calculate the shortest conversion paths
28        for k in range(26):
29            for i in range(26):
30                for j in range(26):
31                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
32      
33        # Initialize total conversion cost
34        total_cost = 0
35      
36        # Calculate total cost of converting source to target
37        for source_char, target_char in zip(source, target):
38            # We only need to calculate cost if the characters are different
39            if source_char != target_char:
40                x, y = ord(source_char) - ord('a'), ord(target_char) - ord('a')
41              
42                # If there is no possible conversion, return -1
43                if graph[x][y] >= inf:
44                    return -1
45              
46                # Add conversion cost to total
47                total_cost += graph[x][y]
48      
49        # Return the total cost of transformation
50        return total_cost
51
1import java.util.Arrays;
2
3public class Solution {
4
5    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
6        final int INFINITY = 1 << 29; // Define a large value to represent infinite cost.
7        int[][] graph = new int[26][26]; // Create a graph to represent the cost of changing one character to another.
8
9        // Initialize the graph with infinite costs, except the diagonal as 0 (cost of changing a char to itself).
10        for (int i = 0; i < 26; ++i) {
11            Arrays.fill(graph[i], INFINITY);
12            graph[i][i] = 0;
13        }
14
15        // Populate the graph with the given costs, taking the minimum if multiple costs are given for the same change.
16        for (int i = 0; i < original.length; ++i) {
17            int fromIndex = original[i] - 'a';
18            int toIndex = changed[i] - 'a';
19            int changeCost = cost[i];
20            graph[fromIndex][toIndex] = Math.min(graph[fromIndex][toIndex], changeCost);
21        }
22
23        // Floyd-Warshall algorithm to find the all-pairs shortest path costs.
24        for (int k = 0; k < 26; ++k) {
25            for (int i = 0; i < 26; ++i) {
26                for (int j = 0; j < 26; ++j) {
27                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
28                }
29            }
30        }
31
32        // Calculate the total minimum cost to transform the source string to the target string.
33        long totalCost = 0;
34        int stringLength = source.length();
35        for (int i = 0; i < stringLength; ++i) {
36            int sourceCharIndex = source.charAt(i) - 'a';
37            int targetCharIndex = target.charAt(i) - 'a';
38            if (sourceCharIndex != targetCharIndex) {
39                // If there is no way to transform the character, return -1.
40                if (graph[sourceCharIndex][targetCharIndex] >= INFINITY) {
41                    return -1;
42                }
43                // Add the cost of the current character transformation.
44                totalCost += graph[sourceCharIndex][targetCharIndex];
45            }
46        }
47        return totalCost;
48    }
49}
50
1class Solution {
2public:
3    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
4        // Define infinity as a large number for initialization purposes
5        const int INF = 1 << 29;
6        int graph[26][26];
7
8        // Initialize the graph with infinity, and 0 for self to self cost
9        for (int i = 0; i < 26; ++i) {
10            fill(begin(graph[i]), end(graph[i]), INF);
11            graph[i][i] = 0;
12        }
13
14        // Construct the graph with the minimum cost between original and changed characters
15        for (int i = 0; i < original.size(); ++i) {
16            int from = original[i] - 'a';
17            int to = changed[i] - 'a';
18            int changeCost = cost[i];
19            graph[from][to] = min(graph[from][to], changeCost);
20        }
21
22        // Floyd-Warshall algorithm to find the shortest path between all pairs of vertices
23        for (int k = 0; k < 26; ++k) {
24            for (int i = 0; i < 26; ++i) {
25                for (int j = 0; j < 26; ++j) {
26                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
27                }
28            }
29        }
30
31        long long totalCost = 0; // total cost for converting source to target
32        int sourceLength = source.length();
33        for (int i = 0; i < sourceLength; ++i) {
34            int sourceChar = source[i] - 'a';
35            int targetChar = target[i] - 'a';
36            // If the characters are different, add the cost to convert them
37            if (sourceChar != targetChar) {
38                // If there is no way to convert the character, return -1
39                if (graph[sourceChar][targetChar] >= INF) {
40                    return -1;
41                }
42                totalCost += graph[sourceChar][targetChar];
43            }
44        }
45        // Return the total minimum cost to convert the source string to the target string
46        return totalCost;
47    }
48};
49
1// Function to calculate the minimum cost to transform the `source` string into the `target` string
2// given the costs of changing individual characters from `original` to `changed`.
3function minimumCost(
4    source: string,
5    target: string,
6    original: string[],
7    changed: string[],
8    cost: number[]
9): number {
10    // Graph 'graph' to store the minimum cost of converting each character to another.
11    // Initialize a 26x26 matrix to represent all possible conversions between alphabets with Infinity,
12    // except for same character conversions which are 0.
13    const graph: number[][] = Array.from({ length: 26 }, () => Array(26).fill(Infinity));
14    for (let i = 0; i < 26; ++i) {
15        graph[i][i] = 0;
16    }
17
18    // Update the graph with the provided costs of changing each character.
19    for (let i = 0; i < original.length; ++i) {
20        const fromCharIndex: number = original[i].charCodeAt(0) - 'a'.charCodeAt(0);
21        const toCharIndex: number = changed[i].charCodeAt(0) - 'a'.charCodeAt(0);
22        const changeCost: number = cost[i];
23        graph[fromCharIndex][toCharIndex] = Math.min(graph[fromCharIndex][toCharIndex], changeCost);
24    }
25
26    // Use Floyd-Warshall algorithm to calculate the shortest paths between all pairs of vertices.
27    for (let k = 0; k < 26; ++k) {
28        for (let i = 0; i < 26; ++i) {
29            for (let j = 0; j < 26; ++j) {
30                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
31            }
32        }
33    }
34
35    // Calculate the total cost to transform `source` into `target` by aggregating costs.
36    let totalCost: number = 0;
37    const sourceLength: number = source.length;
38    for (let i = 0; i < sourceLength; ++i) {
39        const sourceCharIndex: number = source.charCodeAt(i) - 'a'.charCodeAt(0);
40        const targetCharIndex: number = target.charCodeAt(i) - 'a'.charCodeAt(0);
41        // If the characters are different, add the cost to change them.
42        if (sourceCharIndex !== targetCharIndex) {
43            if (graph[sourceCharIndex][targetCharIndex] === Infinity) {
44                // If there's no way to transform the character, return -1.
45                return -1;
46            }
47            totalCost += graph[sourceCharIndex][targetCharIndex];
48        }
49    }
50  
51    // Return the total cost of conversion.
52    return totalCost;
53}
54

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down as follows:

  1. Initialization of the graph: It initializes a 26x26 matrix to inf, except the diagonal which is set to 0. This initialization takes O(|\Sigma|^2) time, where |\Sigma| is the size of the alphabet (26 in this case).

  2. Building the graph: Then, it iterates over the zipped original, changed, and cost arrays to update the graph. Since the arrays' size is m, this part of the process takes O(m) time.

  3. Floyd-Warshall Algorithm: It uses the Floyd-Warshall algorithm to find the shortest path between all pairs of characters. The algorithm has three nested loops each running 26 times (since |\Sigma| = 26), resulting in a time complexity of O(|\Sigma|^3).

  4. Calculating Minimum Cost: Finally, the code iterates over the zipped source and target strings, which in the worst case can be of length n. For each character pair, it checks and sums up the conversion costs. This takes O(n) time, assuming that the access time for each g[x][y] is O(1).

Adding all these parts gives a total time complexity O(m + n + |\Sigma|^3), as stated in the reference answer.

Space Complexity

The space complexity is dominated by the space needed for storing the graph g, which is a 26x26 matrix. Thus, the space complexity is O(|\Sigma|^2).

Here, |\Sigma| represents the size of the alphabet, and in this case, |\Sigma| = 26 as it deals with lowercase English letters. So the space complexity can be specifically stated as O(26^2) which essentially is O(1) because it remains constant regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄