Is Minimum Cost to Convert String I easy or hard?

Minimum Cost to Convert String I is classified as Medium difficulty. The challenge lies in recognizing that character conversions form a weighted graph and that intermediate transformations may reduce total cost.

Minimum Cost to Convert String I Python/Java solution

The problem is commonly implemented in Python, Java, and C++. Python solutions often use a 26x26 matrix for Floyd–Warshall or a priority queue for Dijkstra. Java and C++ implementations typically mirror the same logic with arrays and priority queues.

How to solve Minimum Cost to Convert String I in O(n)?

Precompute the minimum conversion cost between all character pairs using Floyd–Warshall. Once the 26x26 distance matrix is built, iterate through the source and target strings and add the precomputed cost for each pair. Each lookup is O(1), making the final pass O(n).

What is the best approach for Minimum Cost to Convert String I?

The Floyd–Warshall algorithm is the most practical approach because the graph contains only 26 lowercase letters. It precomputes the minimum cost between every pair of characters in O(26^3) time and O(26^2) space. After preprocessing, converting the entire string only requires O(n) lookups.

Is Minimum Cost to Convert String I asked at Google/Amazon/Meta?

Shortest path problems on small graphs frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test whether you recognize graph modeling and apply algorithms such as Dijkstra or Floyd–Warshall efficiently.

What data structure is used in Minimum Cost to Convert String I?

The core structure is a weighted graph where characters are nodes and transformations are edges with costs. Implementations typically use an adjacency list for Dijkstra or a 2D matrix for Floyd–Warshall dynamic programming.

What is the time complexity of Minimum Cost to Convert String I?

Using the optimal Floyd–Warshall solution, the preprocessing cost is O(26^3) and the string traversal takes O(n). Since 26 is constant, the effective complexity becomes O(n). Graph solutions using Dijkstra run in roughly O(26 * (E log V)).

Description Hints 4 Solution Video 16:25

2976. Minimum Cost to Convert String I

Medium63.2% acceptance4 companies

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].

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 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:

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:

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'.

Constraints:

1 <= source.length == target.length <= 10⁵
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 10⁶
original[i] != changed[i]

Asked at 4 companies

Atlassian

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Construct a graph with each letter as a node, and construct an edge (a, b) with weight c if we can change from character a to letter b with cost c. (Keep the one with the smallest cost in case there are multiple edges between a and b).

Hint 2

Calculate the shortest path for each pair of characters (source[i], target[i]). The sum of cost over all i in the range [0, source.length - 1]. If there is no path between source[i] and target[i], the answer is -1.

Hint 3

Any shortest path algorithms will work since we only have 26 nodes. Since we only have at most 26 * 26 pairs, we can save the result to avoid re-calculation.

Hint 4

We can also use Floyd Warshall's algorithm to precompute all the results.

16:25

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution