LeetCode 2976 - Minimum Cost to Convert String I

LeetCode Problem 2976

Difficulty: 🟡 Medium
Topics: Array, String, Graph Theory, Shortest Path

Solution

Problem Understanding

This problem asks us to transform one string into another while minimizing the total conversion cost.

We are given two strings, source and target, both with the same length. Each position in source must eventually become the corresponding character in target. We are also given a list of allowed character transformations. A transformation allows one lowercase letter to be converted into another lowercase letter with a specific cost.

The important detail is that transformations can be chained. Even if there is no direct transformation from 'a' to 'd', it may still be possible to convert 'a' to 'b', then 'b' to 'c', then 'c' to 'd'. The total cost would be the sum of all intermediate transformation costs.

For every index i:

• We start with source[i]
• We need to end with target[i]
• We may apply any number of allowed character conversions
• We want the minimum possible cost

The final answer is the sum of the minimum costs for every position in the string.

If even one position cannot be converted, the entire transformation is impossible, so we return -1.

The constraints reveal an important insight about the problem scale:

• The strings can be very large, up to 10^5
• However, the alphabet contains only 26 lowercase English letters
• The transformation rules are at most 2000

This means we cannot perform an expensive graph search independently for every character position in the string. Instead, we should precompute the minimum conversion cost between every pair of letters once, then reuse that information for all string positions.

Several edge cases are important:

• Multiple rules may exist for the same transformation pair, we must keep the cheapest one.
• Some characters may already match, which costs 0.
• Some conversions may only be possible through intermediate letters.
• Some conversions may be impossible entirely.
• Transformation costs can become large, so we must use sufficiently large integer types. This problem asks us to transform one string into another while minimizing the total conversion cost. Each character in source must eventually match the corresponding character in target. The transformation rules are given through the original, changed, and cost arrays.

Each entry describes a directed conversion:

• original[i] -> changed[i]
• with conversion cost cost[i]

A character may be converted multiple times through intermediate characters. For example, even if there is no direct rule from 'a' to 'b', we may still be able to transform 'a' -> 'c' -> 'b'.

The important detail is that conversions are independent for each character position in the string. Converting source[0] does not affect source[1]. Because of this, the overall answer is simply the sum of the minimum conversion costs for every position.

The input sizes tell us a lot about the intended solution:

• source.length can be as large as 10^5
• there are only 26 lowercase English letters
• conversion rules can be up to 2000

The extremely small alphabet size is the key observation. Even though the strings are large, the graph of possible character transformations contains only 26 nodes.

We can think of the problem as a shortest path problem on a directed weighted graph:

• each lowercase letter is a node
• each conversion rule is a directed edge
• edge weights are conversion costs

For every pair of letters (u, v), we need the minimum cost to convert u into v.

Several edge cases are important:

• Multiple rules may exist for the same conversion pair. We must keep the minimum direct edge cost.
• Some characters may already match. Converting them costs 0.
• Some transformations may only be possible through intermediate characters.
• Some transformations may be impossible entirely, in which case the answer is -1.
• Costs can become large because the string length is up to 10^5, so we must use sufficiently large integer types.

Approaches

Brute Force Approach

A straightforward solution would treat each character position independently.

For every index i, we could run a shortest path algorithm such as Dijkstra's algorithm starting from source[i] to determine the minimum cost to reach target[i].

The graph consists of:

• 26 nodes, one for each lowercase letter
• Directed edges representing allowed transformations

This works because the problem is fundamentally asking for shortest path costs in a weighted directed graph.

For each string position:

1. Start from source[i]
2. Search for the cheapest path to target[i]
3. Add the cost to the answer

This approach is correct because shortest path algorithms guarantee the minimum transformation cost.

However, this becomes inefficient because the strings may contain up to 10^5 characters. Running a graph search for every position repeats the same work many times.

Key Insight

The alphabet size is fixed at only 26 characters.

Instead of solving shortest paths repeatedly, we can precompute the minimum cost between every pair of letters once using the Floyd-Warshall algorithm.

Floyd-Warshall computes all-pairs shortest paths in a graph.

Since there are only 26 nodes:

• The total complexity is only 26^3 = 17576
• This is extremely small and effectively constant time

After precomputing all minimum conversion costs:

• Each string position can be processed in O(1)
• We simply look up the minimum cost from one character to another

This transforms the problem into:

1. Build a 26 × 26 cost matrix
2. Run Floyd-Warshall
3. Sum the minimum costs for all positions

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × (V² or E log V))	O(V + E)	Runs shortest path search for every string position
Optimal	O(26³ + n)	O(26²)	Precomputes all-pairs shortest paths once

Here:

• n is the string length
• V = 26
• E is the number of transformation rules

Algorithm Walkthrough

Optimal Algorithm Using Floyd-Warshall

A naive solution would try to compute the minimum conversion cost separately for every character pair encountered in the strings.

For each position i:

• start from source[i]
• search all possible conversion sequences
• find the cheapest path to target[i]

This can be done using BFS, DFS, or Dijkstra's algorithm repeatedly.

The brute-force method is correct because shortest path algorithms correctly compute minimum path costs in weighted graphs. However, repeatedly running graph searches for up to 10^5 characters becomes inefficient.

Even though the graph only has 26 nodes, repeatedly recomputing shortest paths wastes work because many character pairs repeat.

Key Insight

The graph contains only 26 lowercase English letters. Since the graph is tiny, we can precompute the minimum cost between every pair of letters once.

This immediately suggests an all-pairs shortest path algorithm.

The best fit here is the Floyd-Warshall algorithm because:

• the graph is extremely small
• we need shortest paths between all pairs
• implementation is simple and efficient for 26 nodes

After precomputing the shortest distances between every pair of letters, each string position can be processed in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × (V + E) log V)	O(V + E)	Runs shortest path repeatedly for each character
Optimal	O(26³ + n)	O(26²)	Floyd-Warshall precomputes all conversion costs

Since 26³ = 17576, the preprocessing cost is effectively constant.

Algorithm Walkthrough

1. Create a 26 × 26 distance matrix.

Each entry dist[i][j] represents the minimum known cost to convert character i into character j.

Initially:

• dist[i][i] = 0 because converting a character to itself costs nothing
• All other values are initialized to infinity because they are initially unreachable

2. Insert the direct transformation rules.

For every rule:

• Convert characters into indices from 0 to 25
• Update the matrix with the minimum direct conversion cost

We use the minimum because multiple rules may exist for the same pair. 3. Run the Floyd-Warshall algorithm.

The core idea is to test whether using an intermediate character produces a cheaper conversion.

For every intermediate node k:

• Try improving every pair (i, j)
• Check whether:

dist[i][k] + dist[k][j] < dist[i][j]

If so, update the matrix. 4. Process the strings position by position.

For each index:

• If the characters already match, continue
• Otherwise look up the minimum cost in the matrix
• If the cost is still infinity, return -1
• Otherwise add the cost to the answer

5. Return the total accumulated cost.

Why it works

Floyd-Warshall guarantees that after processing all intermediate nodes, dist[i][j] contains the minimum possible path cost between every pair of vertices.

Since each character transformation corresponds exactly to a graph edge, the matrix eventually stores the cheapest possible conversion between every pair of letters.

Therefore, looking up dist[source[i]][target[i]] gives the true minimum cost for each character position, and summing these values produces the globally minimum total cost.

• set all values to infinity
• set dist[i][i] = 0 because converting a character to itself costs nothing

2. Populate direct conversion costs.

For every rule:

• convert characters into indices 0-25
• update:

dist[u][v] = min(dist[u][v], cost)

We take the minimum because duplicate conversion rules may exist. 3. Run Floyd-Warshall.

For every intermediate character k, attempt to improve every path i -> j using:

$d(i,j)=\min(d(i,j),\ d(i,k)+d(k,j))$

This works because if the cheapest path from i to j goes through k, then combining the best paths i -> k and k -> j produces a better result. 4. Process the strings character by character.

For each index:

• if characters already match, continue
• otherwise look up the precomputed minimum cost

5. Detect impossible transformations.

If:

dist[source][target] == infinity

then no valid transformation exists, so return -1. 6. Accumulate the total cost.

Add the minimum conversion cost for every character position. 7. Return the final answer.

Why it works

Floyd-Warshall guarantees that after processing every intermediate node, dist[i][j] contains the minimum possible path cost between all pairs of vertices.

Since every character transformation corresponds exactly to a path in the graph, the algorithm computes the true minimum conversion cost for every character pair. Summing these independently optimal costs yields the globally minimum total conversion cost for the strings.

Python Solution

from typing import List

class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int]
    ) -> int:
        
        INF = float("inf")
        
        # Distance matrix
        dist = [[INF] * 26 for _ in range(26)]
        
        # Cost to convert a character to itself is 0
        for i in range(26):
            dist[i][i] = 0
        
        # Add direct transformation costs
        for o, c, w in zip(original, changed, cost):
            u = ord(o) - ord('a')
            v = ord(c) - ord('a')
            
            dist[u][v] = min(dist[u][v], w)
        
        # Floyd-Warshall algorithm
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(
                            dist[i][j],
                            dist[i][k] + dist[k][j]
                        )
        
        total_cost = 0
        
        # Compute final answer
        # Cost to convert a character to itself is zero
        for i in range(26):
            dist[i][i] = 0
        
        # Add direct conversion edges
        for o, c, w in zip(original, changed, cost):
            u = ord(o) - ord('a')
            v = ord(c) - ord('a')
            dist[u][v] = min(dist[u][v], w)
        
        # Floyd-Warshall
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] == INF or dist[k][j] == INF:
                        continue
                    
                    new_cost = dist[i][k] + dist[k][j]
                    
                    if new_cost < dist[i][j]:
                        dist[i][j] = new_cost
        
        total_cost = 0
        
        # Compute answer
        for s_char, t_char in zip(source, target):
            if s_char == t_char:
                continue
            
            u = ord(s_char) - ord('a')
            v = ord(t_char) - ord('a')
            
            if dist[u][v] == INF:
                return -1
            
            total_cost += dist[u][v]
        
        return total_cost

The implementation begins by constructing a 26 × 26 adjacency matrix. Every entry initially contains infinity, representing an unreachable conversion.

Next, the diagonal entries are set to 0 because converting a character into itself requires no operations.

The direct transformation rules are then inserted into the matrix. Since duplicate transformations may exist, the implementation stores only the minimum direct cost.

The Floyd-Warshall section computes the minimum conversion cost between all character pairs. Each intermediate node k is tested to determine whether passing through it produces a cheaper path.

Finally, the algorithm iterates through the strings character by character. For every mismatch, it retrieves the precomputed minimum conversion cost from the matrix. If no path exists, the function immediately returns -1. Otherwise, the costs are accumulated and returned. The implementation begins by constructing a 26 × 26 matrix initialized to infinity. This matrix represents the minimum known cost between every pair of characters.

The diagonal entries are set to zero because converting a character into itself requires no operations.

Next, the direct conversion rules are inserted into the matrix. Since duplicate rules may exist, the implementation keeps only the minimum direct edge cost.

The Floyd-Warshall algorithm then computes the shortest paths between all pairs of characters. The triple nested loop systematically checks whether routing through an intermediate character reduces the total conversion cost.

Finally, the code iterates through the strings position by position. If the characters already match, no cost is added. Otherwise, the precomputed shortest path cost is used. If no path exists, the function immediately returns -1.

Go Solution

package main

import "math"

func minimumCost(
	source string,
	target string,
	original []byte,
	changed []byte,
	cost []int,
) int64 {

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
	const INF int64 = math.MaxInt64 / 4

	// Distance matrix
	dist := make([][]int64, 26)
	for i := 0; i < 26; i++ {
		dist[i] = make([]int64, 26)

		for j := 0; j < 26; j++ {
			if i == j {
				dist[i][j] = 0
			} else {
				dist[i][j] = INF
			}
		}
	}

	// Add direct transformation costs
	for i := 0; i < len(cost); i++ {
		u := int(original[i] - 'a')
		v := int(changed[i] - 'a')
			dist[i][j] = INF
		}

		dist[i][i] = 0
	}

	// Add direct edges
	for i := 0; i < len(cost); i++ {
		u := original[i] - 'a'
		v := changed[i] - 'a'
		w := int64(cost[i])

		if w < dist[u][v] {
			dist[u][v] = w
		}
	}

	// Floyd-Warshall
	for k := 0; k < 26; k++ {
		for i := 0; i < 26; i++ {
			for j := 0; j < 26; j++ {

				if dist[i][k] == INF || dist[k][j] == INF {
					continue
				}

				newCost := dist[i][k] + dist[k][j]

				if newCost < dist[i][j] {
					dist[i][j] = newCost
				}
			}
		}
	}

	var total int64 = 0

	// Compute final answer
	for i := 0; i < len(source); i++ {

	var totalCost int64 = 0

	// Compute total answer
	for i := 0; i < len(source); i++ {
		if source[i] == target[i] {
			continue
		}

		u := int(source[i] - 'a')
		v := int(target[i] - 'a')
		u := source[i] - 'a'
		v := target[i] - 'a'

		if dist[u][v] == INF {
			return -1
		}

		total += dist[u][v]
	}

	return total
}

The Go implementation closely mirrors the Python solution, but there are several language-specific considerations.

The distance matrix uses int64 instead of int because total costs can grow large when processing strings of length 10^5.

Go does not provide a built-in infinity constant for integers, so a very large value derived from math.MaxInt64 is used.

The adjacency matrix is created using nested slices. During Floyd-Warshall updates, the implementation skips calculations involving unreachable states to avoid overflow.

The function returns int64, matching the required LeetCode signature. totalCost += dist[u][v] }

return totalCost

}

The Go implementation closely mirrors the Python version, but there are several language-specific considerations.

Go does not have built-in infinity values for integers, so a very large constant is used instead. The implementation uses `int64` everywhere because the total cost can exceed the range of a 32-bit integer.

The distance matrix is implemented using slices of slices. Since Go arrays are fixed size, slices provide more flexibility and cleaner initialization.

The final answer is returned as `int64`, matching the required function signature.

## Worked Examples

### Example 1

source = "abcd" target = "acbe"

Transformation rules:
Initial direct edges:

| From | To | Cost |
| --- | --- | --- |
| a | b | 2 |
| b | c | 5 |
| c | b | 5 |
| c | e | 1 |
| e | b | 2 |
| d | e | 20 |

### Step 1: Initialize Matrix

Initially:

dist[x][x] = 0 all others = INF

### Step 2: Insert Direct Edges

Relevant entries become:

| From | To | Cost |
| --- | --- | --- |
| a | b | 2 |
| b | c | 5 |
| c | b | 5 |
| c | e | 1 |
| e | b | 2 |
| d | e | 20 |

### Step 3: Floyd-Warshall Updates

A key update occurs:

c -> e -> b 1 + 2 = 3

This improves:

dist[c][b] = 3

Another useful path:

b -> c -> e 5 + 1 = 6

So:

dist[b][e] = 6

### Step 4: Process Each Position

| Index | Source | Target | Minimum Cost |
After Floyd-Warshall:

| From | To | Minimum Cost |
| --- | --- | --- |
| a | b | 2 |
| a | c | 7 |
| a | e | 8 |
| b | c | 5 |
| b | e | 6 |
| c | b | 3 |
| c | e | 1 |
| d | e | 20 |

Now process the strings:

| Index | Source | Target | Cost |
| --- | --- | --- | --- |
| 0 | a | a | 0 |
| 1 | b | c | 5 |
| 2 | c | b | 3 |
| 3 | d | e | 20 |

Total:

0 + 5 + 3 + 20 = 28

Answer:

28

## Example 2
### Example 2

source = "aaaa" target = "bbbb"

Rules:
Direct conversions:

| From | To | Cost |
| --- | --- | --- |
| a | c | 1 |
| c | b | 2 |

### Floyd-Warshall Result

The algorithm discovers:

a -> c -> b 1 + 2 = 3

So:

dist[a][b] = 3

### Process String

Each `'a'` becomes `'b'` with cost `3`.

| Position | Cost |
| --- | --- |
| 0 | 3 |
| 1 | 3 |
| 2 | 3 |
| 3 | 3 |

Total:

12

## Example 3
Floyd-Warshall discovers:

| From | To | Minimum Cost |
| --- | --- | --- |
| a | b | 3 |

Each `'a' -> 'b'` costs 3.

There are four positions:

4 × 3 = 12

### Example 3

source = "abcd" target = "abce"

Rules:
Only conversion rule:

| From | To | Cost |
| --- | --- | --- |
| a | e | 10000 |

When processing index `3`:

d -> e

No path exists.

The distance remains infinity, so the algorithm returns:
There is no path from `d` to `e`.

When processing index 3:

| Source | Target | Reachable |
| --- | --- | --- |
| d | e | No |

The algorithm returns:

-1

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(26³ + n) | Floyd-Warshall on 26 letters plus one scan of the strings |
| Space | O(26²) | Distance matrix stores all-pairs costs |

The dominant preprocessing step is Floyd-Warshall, which runs in `O(V³)` where `V = 26`. Since the alphabet size is fixed, this is effectively constant time.

The only input-dependent portion is scanning the strings, which requires `O(n)` time.

The space usage comes entirely from the 26 × 26 distance matrix.
| Time | O(26³ + n) | Floyd-Warshall on 26 nodes plus one pass through the strings |
| Space | O(26²) | Distance matrix storage |

The dominant preprocessing cost comes from Floyd-Warshall. However, because the graph size is fixed at 26 nodes, `26³` is effectively constant.

The linear pass through the strings dominates for large inputs, giving an overall runtime proportional to `n`.

## Test Cases

```python
from typing import List

class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int]
    ) -> int:
        
        INF = float("inf")
        dist = [[INF] * 26 for _ in range(26)]

        for i in range(26):
            dist[i][i] = 0

        
        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 = ord(o) - ord('a')
            v = ord(c) - ord('a')
            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] != INF and dist[k][j] != INF:
                        dist[i][j] = min(
                            dist[i][j],
                            dist[i][k] + dist[k][j]
                        )

        ans = 0

        for s, t in zip(source, target):
            if s == t:
                continue

            u = ord(s) - ord('a')
            v = ord(t) - ord('a')

            if dist[u][v] == INF:
                return -1

            ans += dist[u][v]

        return ans
        
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] == INF or dist[k][j] == INF:
                        continue
                    
                    dist[i][j] = min(
                        dist[i][j],
                        dist[i][k] + dist[k][j]
                    )
        
        total = 0
        
        for s, t in zip(source, target):
            if s == t:
                continue
            
            u = ord(s) - ord('a')
            v = ord(t) - ord('a')
            
            if dist[u][v] == INF:
                return -1
            
            total += dist[u][v]
        
        return total

sol = Solution()

# Example 1
assert sol.minimumCost(
    "abcd",
    "acbe",
    ["a","b","c","c","e","d"],
    ["b","c","b","e","b","e"],
    [2,5,5,1,2,20]
) == 28  # standard multi-step conversion

# Example 2
assert sol.minimumCost(
    "aaaa",
    "bbbb",
    ["a","c"],
    ["c","b"],
    [1,2]
) == 12  # repeated indirect conversion

# Example 3
assert sol.minimumCost(
    "abcd",
    "abce",
    ["a"],
    ["e"],
    [10000]
) == -1  # impossible conversion

# Already identical strings
) == -1  # impossible transformation

# Already equal strings
assert sol.minimumCost(
    "abc",
    "abc",
    ["a"],
    ["b"],
    [1]
) == 0  # no transformations needed

# Direct cheaper than indirect
assert sol.minimumCost(
    "a",
    "c",
    ["a","b","a"],
    ["b","c","c"],
    [5,5,3]
) == 3  # direct path should be chosen

# Indirect cheaper than direct
assert sol.minimumCost(
    "a",
    "c",
    ["a","b","a"],
    ["b","c","c"],
    [1,1,10]
) == 2  # indirect path should be chosen

# Duplicate edges
assert sol.minimumCost(
    "a",
    "b",
    ["a","a"],
    ["b","b"],
    [10,2]
) == 2  # choose minimum duplicate edge

# Large repeated conversion
assert sol.minimumCost(
    "zzzz",
    "aaaa",
    ["z"],
    ["a"],
    [7]
) == 28  # repeated direct conversion

# Multi-hop chain
assert sol.minimumCost(
    "a",
    "e",
    ["a","b","c","d"],
    ["b","c","d","e"],
    [1,1,1,1]
) == 4  # long conversion chain

# Unreachable intermediate
assert sol.minimumCost(
    "a",
    "z",
    ["a","b"],
    ["b","c"],
    [1,1]
) == -1  # no path exists
    [5]
) == 0  # no conversion needed

# Multiple edges between same nodes
assert sol.minimumCost(
    "a",
    "b",
    ["a", "a"],
    ["b", "b"],
    [10, 3]
) == 3  # should choose minimum direct edge

# Indirect path cheaper than direct path
assert sol.minimumCost(
    "a",
    "c",
    ["a", "b", "a"],
    ["b", "c", "c"],
    [2, 2, 10]
) == 4  # indirect route is cheaper

# Single character impossible
assert sol.minimumCost(
    "a",
    "z",
    ["a"],
    ["b"],
    [1]
) == -1  # no valid path

# Large repeated conversions
assert sol.minimumCost(
    "aaaaa",
    "ccccc",
    ["a", "b"],
    ["b", "c"],
    [1, 1]
) == 10  # repeated shortest path use

# Self transformation only
assert sol.minimumCost(
    "z",
    "z",
    [],
    [],
    []
) == 0  # zero cost for identical chars

Test	Why
Example 1	Validates standard shortest path behavior
Example 2	Validates repeated indirect transformations
Example 3	Validates impossible conversion detection
Identical strings	Ensures zero-cost matches are handled
Direct cheaper than indirect	Confirms minimum direct edge selection
Indirect cheaper than direct	Confirms shortest path logic
Duplicate edges	Ensures duplicate rules use minimum cost
Large repeated conversion	Tests accumulation across many positions
Multi-hop chain	Tests longer transformation paths
Unreachable intermediate	Confirms unreachable detection

Edge Cases

Duplicate Transformation Rules

The input may contain multiple rules for the same transformation pair.

For example:

a -> b cost 10
a -> b cost 3

A naive implementation might overwrite values incorrectly depending on insertion order. The correct behavior is to keep the minimum direct edge cost.

The implementation handles this using:

dist[u][v] = min(dist[u][v], w)

This guarantees the graph starts with the cheapest direct conversion.

Characters Already Match

Some positions may already contain the desired character.

For example:

source[i] == target[i]

No transformation should occur, and the cost contribution should be 0.

A buggy implementation might accidentally attempt graph lookup or incorrectly return -1.

The solution explicitly skips such positions:

if s_char == t_char:
    continue

Impossible Transformations

Some character pairs may not have any valid conversion path.

For example:

a -> b
b -> c

Trying to convert:

a -> z

is impossible.

The Floyd-Warshall matrix keeps unreachable pairs as infinity. During final processing, the implementation checks:

if dist[u][v] == INF:
    return -1

This guarantees the function immediately detects impossible transformations.

Indirect Paths Cheaper Than Direct Paths

A direct conversion is not always optimal.

Example:

a -> c cost 10
a -> b cost 2
b -> c cost 2

The best route is:

a -> b -> c

with total cost 4.

A greedy approach considering only direct edges would fail here. Floyd-Warshall correctly computes the minimum path over all possible intermediates. | Example 1 | Validates multi-step shortest path behavior | | Example 2 | Verifies repeated indirect conversions | | Example 3 | Confirms impossible transformations return -1 | | Equal strings | Ensures zero-cost handling | | Duplicate edges | |