Minimum Cost to Convert String I

Minimum Cost to Convert String I

What is this problem about?

The Minimum Cost to Convert String I problem gives you a source string and a target string of the same length. You are also given a set of transformation rules: you can change character a to b for a specific cost. You can apply any number of transformations (e.g., a -> b -> c). You need to find the minimum total cost to convert the entire source string into the target string.

Why is this asked in interviews?

This is a standard Minimum Cost to Convert String interview question at Google and Amazon. It is a "Shortest Path" problem hidden as a string problem. It tests if you can model the 26 lowercase letters as nodes in a graph and use the Floyd-Warshall Algorithm to find the minimum cost between any two characters.

Algorithmic pattern used

The Floyd-Warshall interview pattern is the most effective.

1. Create a $26 \times 26$ cost matrix initialized to infinity.
2. Fill the matrix with the given transformation costs.
3. Run Floyd-Warshall to find the all-pairs shortest path in $O(26^3)$ time.
4. Iterate through source and target strings character by character, adding the precomputed cost to the total.

Example explanation

Source: "abc", Target: "abd". Rules: 'c' to 'e' cost 1, 'e' to 'd' cost 2.

1. Floyd-Warshall finds the path 'c' -> 'e' -> 'd' with cost 1 + 2 = 3.
2. Total cost = cost('a'->'a') + cost('b'->'b') + cost('c'->'d') = 0 + 0 + 3 = 3.

Common mistakes candidates make

• Running Dijkstra for every character: If the string is long, running a graph search for every index is redundant. Floyd-Warshall is better because there are only 26 nodes.
• Ignoring intermediate steps: Forgetting that a -> c might be cheaper via a -> b -> c than a direct a -> c rule.
• Not handling unreachable characters: If a character cannot be converted, the problem usually requires returning -1.

Interview preparation tip

Any time you have transformations between a small, fixed set of states (like characters 'a'-'z'), precompute an All-Pairs Shortest Path matrix. This makes subsequent lookups $O(1)$ and significantly simplifies the main logic.