Problem Description

You have two strings source and target of equal length n, both containing only lowercase English letters. You want to transform source into target using character replacements.

You're given three arrays that define the available character transformations:

• original[i]: a character that can be changed
• changed[i]: what the character can be changed to
• cost[i]: the cost of changing original[i] to changed[i]

In each operation, you can pick any character x in your current string and change it to character y if there exists an index j where:

• original[j] = x
• changed[j] = y
• The operation costs cost[j]

Note that the same character transformation (from x to y) might appear multiple times with different costs - you can choose any available option.

Your task is to find the minimum total cost to convert source to target. If it's impossible to do so, return -1.

For example, if source = "abc" and target = "adc", you need to change the character at position 1 from 'b' to 'd'. If there's a transformation available from 'b' to 'd' with cost 3, then the minimum cost would be 3. However, you might also chain transformations - for instance, if 'b' can change to 'e' with cost 1, and 'e' can change to 'd' with cost 1, then the minimum cost would be 2.

The solution uses Floyd-Warshall algorithm to find the shortest path (minimum cost) between any two characters, treating each character as a node in a graph and transformations as weighted directed edges.

Intuition

The key insight is recognizing this as a graph problem where we need to find the minimum cost path between characters.

Think of each lowercase letter as a node in a graph. The given transformations create directed edges between these nodes, where the edge weight represents the transformation cost. When we need to change a character in source to match the corresponding character in target, we're essentially asking: "What's the cheapest way to get from node (source character) to node (target character)?"

The crucial observation is that we might not always have a direct transformation available. For instance, to change 'a' to 'c', we might not have a direct 'a' → 'c' transformation, but we could have 'a' → 'b' with cost 2 and 'b' → 'c' with cost 3, giving us a total cost of 5. This means we need to consider paths that go through intermediate characters.

Since we only have 26 possible characters (nodes), we can precompute the minimum cost between every pair of characters. This is a classic "all-pairs shortest path" problem. Floyd-Warshall algorithm is perfect here because:

1. We have a small, dense graph (only 26 nodes)
2. We need the shortest paths between all pairs of nodes
3. The algorithm handles the case where multiple edges exist between the same pair of nodes (we just keep the minimum cost)

Once we've computed the minimum transformation cost between every pair of characters using Floyd-Warshall, converting source to target becomes straightforward. For each position where the characters differ, we look up the precomputed minimum cost. If any character can't be transformed (cost is infinity), the entire transformation is impossible.

The time complexity of Floyd-Warshall is O(26³) which is constant, and checking each character pair in the strings takes O(n), making this approach efficient.

Learn more about Graph and Shortest Path patterns.

Solution Approach

We implement the solution using Floyd-Warshall algorithm to find minimum transformation costs between all character pairs.

Step 1: Initialize the Cost Matrix

Create a 26×26 matrix g where g[i][j] represents the minimum cost to transform character i to character j:

• Initialize all values to infinity: g[i][j] = inf
• Set diagonal to 0 since transforming a character to itself costs nothing: g[i][i] = 0

g = [[inf] * 26 for _ in range(26)]
for i in range(26):
    g[i][i] = 0

Step 2: Populate Direct Transformation Costs

Process the input arrays original, changed, and cost. For each transformation:

• Convert characters to indices (0-25) using ord(x) - ord('a')
• Update the matrix with the minimum cost for each transformation (handling duplicates)

for x, y, z in zip(original, changed, cost):
    x = ord(x) - ord('a')
    y = ord(y) - ord('a')
    g[x][y] = min(g[x][y], z)

Step 3: Apply Floyd-Warshall Algorithm

Find the shortest paths between all pairs of characters by considering intermediate nodes:

• For each intermediate character k
• For each source character i and destination character j
• Check if going through k gives a cheaper path: g[i][j] = min(g[i][j], g[i][k] + g[k][j])

for k in range(26):
    for i in range(26):
        for j in range(26):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

Step 4: Calculate Total Transformation Cost

Traverse source and target strings simultaneously:

• If characters at position match, no cost needed
• If they differ, look up the minimum transformation cost from g
• If transformation cost is infinity, return -1 (impossible)
• Otherwise, add the cost to the running total

ans = 0
for a, b in zip(source, target):
    if a != b:
        x, y = ord(a) - ord('a'), ord(b) - ord('a')
        if g[x][y] >= inf:
            return -1
        ans += g[x][y]
return ans

The algorithm efficiently handles:

• Multiple paths between characters (keeps minimum)
• Indirect transformations through intermediate characters
• Impossible transformations (returns -1)

Time Complexity: O(26³ + n + m) where n is string length and m is the number of transformations Space Complexity: O(26²) for the cost matrix

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• source = "abc"
• target = "aec"
• original = ['b', 'b', 'c']
• changed = ['e', 'c', 'e']
• cost = [2, 5, 1]

This means we have three transformations available:

1. 'b' → 'e' with cost 2
2. 'b' → 'c' with cost 5
3. 'c' → 'e' with cost 1

Step 1: Initialize Cost Matrix

We create a 26×26 matrix (we'll show only relevant characters a-e for brevity):

    a   b   c   d   e
a   0   ∞   ∞   ∞   ∞
b   ∞   0   ∞   ∞   ∞
c   ∞   ∞   0   ∞   ∞
d   ∞   ∞   ∞   0   ∞
e   ∞   ∞   ∞   ∞   0

Step 2: Add Direct Transformations

Process each transformation:

• 'b' → 'e' with cost 2: g[1][4] = 2
• 'b' → 'c' with cost 5: g[1][2] = 5
• 'c' → 'e' with cost 1: g[2][4] = 1

Matrix becomes:

    a   b   c   d   e
a   0   ∞   ∞   ∞   ∞
b   ∞   0   5   ∞   2
c   ∞   ∞   0   ∞   1
d   ∞   ∞   ∞   0   ∞
e   ∞   ∞   ∞   ∞   0

Step 3: Floyd-Warshall Algorithm

Consider paths through intermediate nodes. Key discovery:

• When k='c' (index 2), we check if 'b' → 'c' → 'e' is cheaper than 'b' → 'e'
• Current: g[b][e] = 2
• Via 'c': g[b][c] + g[c][e] = 5 + 1 = 6
• Keep the minimum: g[b][e] = 2

After Floyd-Warshall, we have all shortest paths between characters.

Step 4: Calculate Total Cost

Compare source = "abc" with target = "aec":

Position 0: 'a' vs 'a' → Match, cost = 0 Position 1: 'b' vs 'e' → Need transformation

• Look up g[b][e] = 2
• Add to total: cost = 2

Position 2: 'c' vs 'c' → Match, cost = 0

Result: Total minimum cost = 2

Note: If we needed to transform 'b' to 'd' but had no path available (direct or indirect), g[b][d] would remain infinity and we'd return -1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n + |Σ|³) where:

• m is the length of the original array (same as changed and cost arrays)
• n is the length of the source string (same as target string)
• |Σ| = 26 represents the size of the alphabet (26 lowercase English letters)

The time complexity breaks down as follows:

• Initializing the graph g with infinity values: O(|Σ|²) = O(26²)
• Setting diagonal elements to 0: O(|Σ|) = O(26)
• Processing all transformation costs from original to changed: O(m) iterations, each with O(1) operations
• Floyd-Warshall algorithm to find shortest paths: O(|Σ|³) = O(26³) with three nested loops
• Computing the minimum cost by iterating through source and target: O(n) iterations, each with O(1) lookup

Overall: O(26² + 26 + m + 26³ + n) = O(m + n + |Σ|³)

Space Complexity: O(|Σ|²) where |Σ| = 26

The space complexity is determined by:

• The 2D graph matrix g of size 26 × 26: O(|Σ|²) = O(26²)
• Other variables use constant space: O(1)

Overall: O(|Σ|²) = O(26²)

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

Common Pitfalls

1. Not Handling Multiple Transformation Costs Between Same Character Pairs

Pitfall: A critical mistake is overwriting transformation costs instead of keeping the minimum when the same character transformation appears multiple times in the input.

Incorrect Implementation:

# Wrong: This overwrites previous costs
for x, y, z in zip(original, changed, cost):
    x = ord(x) - ord('a')
    y = ord(y) - ord('a')
    g[x][y] = z  # ❌ Overwrites existing value

Why It's Wrong: If the input contains:

• original = ['a', 'a'], changed = ['b', 'b'], cost = [5, 2]
• The second transformation would overwrite the first, keeping cost 2
• But what if the order was reversed? We'd keep cost 5 instead of 2

Correct Implementation:

# Correct: Keep the minimum cost
for x, y, z in zip(original, changed, cost):
    x = ord(x) - ord('a')
    y = ord(y) - ord('a')
    g[x][y] = min(g[x][y], z)  # ✅ Keeps minimum

2. Incorrect Infinity Value Handling

Pitfall: Using a numeric value that's too small as "infinity" or not properly checking for unreachable paths.

Incorrect Implementation:

# Wrong: Using a small value as infinity
INF = 10**6  # ❌ Might be too small for some inputs
g = [[INF] * 26 for _ in range(26)]

# Later in the code:
if g[x][y] == INF:  # ❌ Exact equality check is fragile
    return -1

Why It's Wrong:

• If costs sum up beyond your chosen "infinity" value, the algorithm breaks
• After Floyd-Warshall, the value might be slightly different due to additions

Correct Implementation:

from math import inf

# Correct: Use Python's built-in infinity
g = [[inf] * 26 for _ in range(26)]

# Check with comparison, not equality
if g[x][y] >= inf:  # ✅ Handles infinity properly
    return -1

3. Forgetting to Initialize Self-Transformations to Zero

Pitfall: Not setting the diagonal of the cost matrix to 0, which represents the cost of "transforming" a character to itself.

Incorrect Implementation:

# Wrong: Forgetting to initialize diagonal
g = [[inf] * 26 for _ in range(26)]
# ❌ Missing: g[i][i] = 0

Why It's Wrong:

• Floyd-Warshall assumes zero cost for self-loops
• Without this, paths that go through the same character would have infinite cost
• This breaks the algorithm's ability to find indirect paths

Correct Implementation:

g = [[inf] * 26 for _ in range(26)]
# Correct: Initialize diagonal to 0
for i in range(26):
    g[i][i] = 0  # ✅ Essential for Floyd-Warshall

4. Processing Characters That Are Already Equal

Pitfall: Attempting to look up transformation costs for characters that are already the same, potentially adding unnecessary costs or causing errors.

Incorrect Implementation:

# Wrong: Always looking up transformation cost
total_cost = 0
for a, b in zip(source, target):
    x, y = ord(a) - ord('a'), ord(b) - ord('a')
    # ❌ This adds cost even when a == b
    total_cost += g[x][y]

Why It's Wrong:

• When a == b, we shouldn't add any cost
• Even though g[i][i] = 0, it's inefficient and conceptually wrong

Correct Implementation:

total_cost = 0
for a, b in zip(source, target):
    if a != b:  # ✅ Only process different characters
        x, y = ord(a) - ord('a'), ord(b) - ord('a')
        if g[x][y] >= inf:
            return -1
        total_cost += g[x][y]