2976. Minimum Cost to Convert String I

The problem

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]

Approach overview

Problem Overview: You are given two strings source and target of equal length and a list of character transformations with associated costs. Each operation converts one character into another. The goal is to compute the minimum total cost to transform source into target. If any position cannot be converted through the given rules, return -1.

Approach 1: Graph Based Shortest Path (O(V * E), Space O(V + E))

Treat each character as a node in a directed weighted graph. Each transformation rule a -> b with cost c becomes an edge. For every character pair needed in the strings, compute the shortest path from the source character to the target character. A simple shortest-path traversal from each starting character accumulates the minimal conversion cost. This works because character conversions may require intermediate steps such as a -> c -> d. The approach models the problem directly as a graph traversal.

Approach 2: Dynamic Programming with Floyd-Warshall (O(26^3), Space O(26^2))

Since the alphabet size is fixed (26 lowercase letters), compute the minimum conversion cost between every pair of characters using the Floyd–Warshall algorithm. Initialize a 26 x 26 matrix with direct transformation costs, then iteratively update using the relation dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). This dynamic programming approach efficiently finds the shortest paths between all pairs of nodes in a shortest path problem. After preprocessing, iterate through the strings and sum the cost for each character conversion.

Approach 3: Graph-based Approach with Dijkstra's Algorithm (O(26 * (E log V)), Space O(V + E))

Build a weighted adjacency list for character transformations and run Dijkstra's algorithm from each character that appears in source. Dijkstra guarantees the optimal path in graphs with non-negative weights. Cache the computed shortest distances so repeated conversions reuse the result. This approach scales well if the transformation rules grow larger and mirrors typical interview solutions for weighted graph problems.

Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path (O(26^3), Space O(26^2))

This is the most direct solution when the node set is small and fixed. Precompute minimal costs between every pair of characters using the Floyd–Warshall all-pairs algorithm. Once the matrix is ready, each string position becomes a constant-time lookup. The overall runtime is dominated by the preprocessing step, which remains effectively constant due to the small alphabet size.

Recommended for interviews: Floyd–Warshall is usually the cleanest answer because the character set is limited to 26 nodes. Interviewers like this observation because it reduces repeated shortest-path searches into a single preprocessing step. Explaining the graph model first shows strong problem understanding, while implementing the Floyd–Warshall optimization demonstrates algorithmic maturity.

Approach 1: Graph Based Shortest Path Approach

In this approach, we can model the problem as a graph where each character is a node, and directed edges with weights indicate a transformation from one character to another. The edges represent 'original to changed' characters with the given cost. To achieve the transformation from source to target, we need to find the minimum cost path for each position in the source string.

We can utilize Dijkstra's algorithm to find the shortest path from each character in source[i] to target[i] based on the transformation rules. For each character transformation, attempt to find the minimum cost path to transform each character accordingly.

Python

import heapq
from collections import defaultdict

def minCostToConvert(source, target, original, changed, cost):
    n = len(source)
    graph = defaultdict(list)

    # Building the graph
    for o, c, w in zip(original, changed, cost):
        graph[o].append((c, w))

    def dijkstra(start, end):
        pq = [(0, start)]  # (cost, node)
        visited = set()

        while pq:
            curr_cost, u = heapq.heappop(pq)
            if u == end:
                return curr_cost
            if u in visited:
                continue
            visited.add(u)
            for v, weight in graph[u]:
                if v not in visited:
                    heapq.heappush(pq, (curr_cost + weight, v))
        return float('inf')

    total_cost = 0

    for s, t in zip(source, target):
        if s == t:
            continue
        min_cost = dijkstra(s, t)
        if min_cost == float('inf'):
            return -1
        total_cost += min_cost

    return total_cost

dijkstra function is used to find the shortest transformation cost from one character to another. It utilizes a min-heap priority queue to efficiently extract the minimum path cost fascinatingly similar to Dijkstra's algorithm for shortest path in graphs. For each character of the source and target, it calculates the minimum transformation cost.

Complexity

Time Complexity: O(n * (V + E) log V) where V is the number of unique characters (vertices) and E is the number of transformation rules (edges).
Space Complexity: O(V + E) for graph representation and auxiliary data structures.

Try this approach in the editor

Approach 2: Dynamic Programming with Floyd-Warshall

This approach involves using the Floyd-Warshall algorithm to pre-compute the shortest transformation cost between any two characters. Consider this as an all-pairs shortest path where each character is a node in the graph, and transformations provide weighted edges. First, apply Floyd-Warshall to compute minimum transformation costs between characters. Then, for each character in the source string, find the transformation cost to match the target using pre-computed values.

Python

def minCostToConvert(source, target, original, changed, cost):
    import sys
    inf = sys.maxsize
    char_count = 26 # a-z
    dp = [[inf] * char_count for _ in range(char_count)]

    # Initialize cost for self to self as 0
    for i in range(char_count):
        dp[i][i] = 0

    # Build initial graph costs
    for o, c, w in zip(original, changed, cost):
        dp[ord(o) - ord('a')][ord(c) - ord('a')] = min(dp[ord(o) - ord('a')][ord(c) - ord('a')], w)

    # Floyd-Warshall for shortest paths
    for k in range(char_count):
        for i in range(char_count):
            for j in range(char_count):
                if dp[i][k] < inf and dp[k][j] < inf:  # Avoid overflow or needless comparisons
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    total_cost = 0
    n = len(source)

    for i in range(n):
        src = ord(source[i]) - ord('a')
        tar = ord(target[i]) - ord('a')
        if src == tar:
            continue
        if dp[src][tar] == inf:
            return -1
        total_cost += dp[src][tar]

    return total_cost

The Dynamic Programming table dp is filled using the character to character transformation cost. Initial direct transformation costs are added using the problem's input, followed by updates using the Floyd-Warshall algorithm to include indirect transformations for building comprehensive paths.

Complexity

Time Complexity: O(n + V^3), where n is the string length and V is the number of unique characters (26 for lowercase alphabets).
Space Complexity: O(V^2) for storing the distance transformation table.

Try this approach in the editor

Approach 3: Graph-based Approach with Dijkstra's Algorithm

The primary idea is to use a graph where each letter is a node, and transformations are directed edges with weights (costs). We can use Dijkstra's algorithm to find the shortest path (minimum cost) to convert each character from source to the corresponding character in target.

Python

import heapq
from collections import defaultdict

def min_cost_to_convert(source, target, original, changed, cost):
    if len(source) != len(target): return -1
    graph = defaultdict(list)
    for o, c, w in zip(original, changed, cost):
        graph[o].append((c, w))
    
    def dijkstra(src, tgt):
        heap = [(0, src)]
        min_cost = {src: 0}
        while heap:
            current_cost, u = heapq.heappop(heap)
            if u == tgt:
                return current_cost
            for v, weight in graph[u]:
                if v not in min_cost or current_cost + weight < min_cost[v]:
                    min_cost[v] = current_cost + weight
                    heapq.heappush(heap, (current_cost + weight, v))
        return float('inf')  # Impossible to transform
    
    total_cost = 0
    for s, t in zip(source, target):
        if s == t:
            continue
        cost_to_transform = dijkstra(s, t)
        if cost_to_transform == float('inf'):
            return -1
        total_cost += cost_to_transform
    return total_cost

Java

import java.util.*;

class Solution {
    public int minCostToConvert(String source, String target, char[] original, char[] changed, int[] cost) {
        if (source.length() != target.length()) return -1;
        Map<Character, List<int[]>> graph = new HashMap<>();
        for (int i = 0; i < original.length; i++) {
            graph.computeIfAbsent(original[i], k -> new ArrayList<>()).add(new int[]{changed[i], cost[i]});
        }

        return transformCost(source, target, graph);
    }

    private int transformCost(String source, String target, Map<Character, List<int[]>> graph) {
        int totalCost = 0;
        for (int i = 0; i < source.length(); i++) {
            if (source.charAt(i) == target.charAt(i)) continue;
            int cost = dijkstra(source.charAt(i), target.charAt(i), graph);
            if (cost == Integer.MAX_VALUE) return -1;
            totalCost += cost;
        }
        return totalCost;
    }

    private int dijkstra(char start, char end, Map<Character, List<int[]>> graph) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        Map<Character, Integer> minCost = new HashMap<>();
        minHeap.offer(new int[]{0, start});
        minCost.put(start, 0);

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int currentCost = curr[0];
            char u = (char) curr[1];
            if (u == end) return currentCost;

            if (!graph.containsKey(u)) continue;

            for (int[] neighbor : graph.get(u)) {
                char v = (char) neighbor[0];
                int weight = neighbor[1];
                int newCost = currentCost + weight;
                if (!minCost.containsKey(v) || newCost < minCost.get(v)) {
                    minCost.put(v, newCost);
                    minHeap.offer(new int[]{newCost, v});
                }
            }
        }
        return Integer.MAX_VALUE;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int minCostToConvert(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
    if (source.size() != target.size()) return -1;
    unordered_map<char, vector<pair<char, int>>> graph;
    for (size_t i = 0; i < original.size(); ++i) {
        graph[original[i]].emplace_back(changed[i], cost[i]);
    }

    auto dijkstra = [&](char src, char tgt) {
        priority_queue<pair<int, char>, vector<pair<int, char>>, greater<>> minHeap;
        unordered_map<char, int> minCost;
        minHeap.emplace(0, src);
        minCost[src] = 0;

        while (!minHeap.empty()) {
            auto [currentCost, u] = minHeap.top(); minHeap.pop();
            if (u == tgt) return currentCost;
            for (auto& [v, weight] : graph[u]) {
                if (!minCost.count(v) || currentCost + weight < minCost[v]) {
                    minCost[v] = currentCost + weight;
                    minHeap.emplace(currentCost + weight, v);
                }
            }
        }
        return INT_MAX;  // Impossible
    };

    int totalCost = 0;
    for (size_t i = 0; i < source.size(); ++i) {
        if (source[i] == target[i]) continue;
        int costToTransform = dijkstra(source[i], target[i]);
        if (costToTransform == INT_MAX) return -1;
        totalCost += costToTransform;
    }
    return totalCost;
}

The Python solution uses the Dijkstra's algorithm to find the minimum cost path between each letter that needs transformation. We maintain a priority queue to efficiently extract the minimum cost transformation at each step.

Complexity

Time Complexity: O(M log C) per pair of letters to transform, where M is the number of edges (transformations) and C is the total graph nodes (the alphabet size). Space Complexity: O(C + M).

Try this approach in the editor

Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path

This approach utilizes the Floyd-Warshall algorithm to precompute the minimum cost from every character to every other character. This is helpful as we need to transform multiple characters efficiently.

Python

def min_cost_to_convert(source, target, original, changed, cost):
    INF = float('inf')
    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):
        dist[ord(o) - ord('a')][ord(c) - ord('a')] = min(w, dist[ord(o) - ord('a')][ord(c) - ord('a')])
    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
    for s, t in zip(source, target):
        if s == t:
            continue
        cost_to_transform = dist[ord(s) - ord('a')][ord(t) - ord('a')]
        if cost_to_transform == INF:
            return -1
        total_cost += cost_to_transform
    return total_cost

Java

class Solution {
    public int minCostToConvert(String source, String target, char[] original, char[] changed, int[] cost) {
        final int INF = 1_000_000_000;
        int[][] dist = new int[26][26];
        for (int i = 0; i < 26; i++)
            Arrays.fill(dist[i], INF);
        for (int i = 0; i < 26; i++)
            dist[i][i] = 0;
        for (int i = 0; i < original.length; i++) {
            int u = original[i] - 'a', v = changed[i] - 'a';
            dist[u][v] = Math.min(dist[u][v], cost[i]);
        }
        for (int k = 0; k < 26; k++)
            for (int i = 0; i < 26; i++)
                for (int j = 0; j < 26; j++)
                    if (dist[i][k] < INF && dist[k][j] < INF)
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

        int totalCost = 0;
        for (int i = 0; i < source.length(); i++) {
            if (source.charAt(i) == target.charAt(i)) continue;
            int costToTransform = dist[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
            if (costToTransform == INF) return -1;
            totalCost += costToTransform;
        }
        return totalCost;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int minCostToConvert(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
    const int INF = 1e9;
    vector<vector<int>> dist(26, vector<int>(26, INF));
    for (int i = 0; i < 26; ++i) dist[i][i] = 0;
    
    for (size_t i = 0; i < original.size(); ++i) {
        int u = original[i] - 'a', v = changed[i] - 'a';
        dist[u][v] = min(dist[u][v], cost[i]);
    }

    for (int k = 0; k < 26; ++k)
        for (int i = 0; i < 26; ++i)
            for (int j = 0; j < 26; ++j)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int total_cost = 0;
    for (size_t i = 0; i < source.size(); ++i) {
        if (source[i] == target[i]) continue;
        int cost_to_transform = dist[source[i] - 'a'][target[i] - 'a'];
        if (cost_to_transform == INF) return -1;
        total_cost += cost_to_transform;
    }
    return total_cost;
}

This Python solution precomputes shortest paths for any character transformation using Floyd-Warshall. We map characters to indices (0 to 25) representing the alphabet.

Complexity

Time Complexity: O(26^3 + N), Space Complexity: O(26^2).

Try this approach in the editor

Approach 5: Floyd Algorithm

According to the problem description, we can consider each letter as a node, and the conversion cost between each pair of letters as a directed edge. We first initialize a 26 times 26 two-dimensional array g, where g[i][j] represents the minimum cost of converting letter i to letter j. Initially, g[i][j] = infty, and if i = j, then g[i][j] = 0.

Next, we traverse the arrays original, changed, and cost. For each index i, we update the cost cost[i] of converting original[i] to changed[i] to g[original[i]][changed[i]], taking the minimum value.

Then, we use the Floyd algorithm to calculate the minimum cost between any two nodes in g. Finally, we traverse the strings source and target. If source[i] neq target[i] and g[source[i]][target[i]] geq infty, it means that the conversion cannot be completed, so we return -1. Otherwise, we add g[source[i]][target[i]] to the answer.

After the traversal ends, we return the answer.

JavaScript

/**
 * @param {string} source
 * @param {string} target
 * @param {character[]} original
 * @param {character[]} changed
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function (source, target, original, changed, cost) {
    const [n, m, MAX] = [source.length, original.length, Number.POSITIVE_INFINITY];
    const g = Array.from({ length: 26 }, () => Array(26).fill(MAX));
    const getIndex = ch => ch.charCodeAt(0) - 'a'.charCodeAt(0);

    for (let i = 0; i < 26; ++i) g[i][i] = 0;
    for (let i = 0; i < m; ++i) {
        const x = getIndex(original[i]);
        const y = getIndex(changed[i]);
        const z = cost[i];
        g[x][y] = Math.min(g[x][y], z);
    }

    for (let k = 0; k < 26; ++k) {
        for (let i = 0; i < 26; ++i) {
            for (let j = 0; g[i][k] < MAX && j < 26; j++) {
                if (g[k][j] < MAX) {
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
    }

    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const x = getIndex(source[i]);
        const y = getIndex(target[i]);
        if (x === y) continue;
        if (g[x][y] === MAX) return -1;
        ans += g[x][y];
    }
    return ans;
};

TypeScript

function minimumCost(
    source: string,
    target: string,
    original: string[],
    changed: string[],
    cost: number[],
): number {
    const [n, m, MAX] = [source.length, original.length, Number.POSITIVE_INFINITY];
    const g: number[][] = Array.from({ length: 26 }, () => Array(26).fill(MAX));
    const getIndex = (ch: string) => ch.charCodeAt(0) - 'a'.charCodeAt(0);

    for (let i = 0; i < 26; ++i) g[i][i] = 0;
    for (let i = 0; i < m; ++i) {
        const x = getIndex(original[i]);
        const y = getIndex(changed[i]);
        const z = cost[i];
        g[x][y] = Math.min(g[x][y], z);
    }

    for (let k = 0; k < 26; ++k) {
        for (let i = 0; i < 26; ++i) {
            for (let j = 0; g[i][k] < MAX && j < 26; j++) {
                if (g[k][j] < MAX) {
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
    }

    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const x = getIndex(source[i]);
        const y = getIndex(target[i]);
        if (x === y) continue;
        if (g[x][y] === MAX) return -1;
        ans += g[x][y];
    }
    return ans;
}

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) (ans int64) {
	const inf = 1 << 29
	g := make([][]int, 26)
	for i := range g {
		g[i] = make([]int, 26)
		for j := range g[i] {
			if i == j {
				g[i][j] = 0
			} else {
				g[i][j] = inf
			}
		}
	}

	for i := 0; i < len(original); i++ {
		x := int(original[i] - 'a')
		y := int(changed[i] - 'a')
		z := cost[i]
		g[x][y] = min(g[x][y], z)
	}

	for k := 0; k < 26; k++ {
		for i := 0; i < 26; i++ {
			for j := 0; j < 26; j++ {
				g[i][j] = min(g[i][j], g[i][k]+g[k][j])
			}
		}
	}
	n := len(source)
	for i := 0; i < n; i++ {
		x := int(source[i] - 'a')
		y := int(target[i] - 'a')
		if x != y {
			if g[x][y] >= inf {
				return -1
			}
			ans += int64(g[x][y])
		}
	}
	return
}

Rust

impl Solution {
    pub fn minimum_cost(
        source: String,
        target: String,
        original: Vec<char>,
        changed: Vec<char>,
        cost: Vec<i32>,
    ) -> i64 {
        let inf: i64 = i64::MAX / 4;
        let mut g = vec![vec![inf; 26]; 26];

        for i in 0..26 {
            g[i][i] = 0;
        }

        for i in 0..original.len() {
            let x = (original[i] as u8 - b'a') as usize;
            let y = (changed[i] as u8 - b'a') as usize;
            g[x][y] = g[x][y].min(cost[i] as i64);
        }

        for k in 0..26 {
            for i in 0..26 {
                for j in 0..26 {
                    let v = g[i][k] + g[k][j];
                    if v < g[i][j] {
                        g[i][j] = v;
                    }
                }
            }
        }

        let mut ans: i64 = 0;
        for (a, b) in source.bytes().zip(target.bytes()) {
            if a != b {
                let x = (a - b'a') as usize;
                let y = (b - b'a') as usize;
                if g[x][y] >= inf {
                    return -1;
                }
                ans += g[x][y];
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Graph Based Shortest Path Approach	Time Complexity: O(n * (V + E) log V) where V is the number of unique characters (vertices) and E is the number of transformation rules (edges). Space Complexity: O(V + E) for graph representation and auxiliary data structures.
Dynamic Programming with Floyd-Warshall	Time Complexity: O(n + V^3), where n is the string length and V is the number of unique characters (26 for lowercase alphabets). Space Complexity: O(V^2) for storing the distance transformation table.
Graph-based Approach with Dijkstra's Algorithm	Time Complexity: O(M log C) per pair of letters to transform, where M is the number of edges (transformations) and C is the total graph nodes (the alphabet size). Space Complexity: O(C + M).
Floyd-Warshall Algorithm for All-Pairs Shortest Path	Time Complexity: O(26^3 + N), Space Complexity: O(26^2).
Floyd Algorithm	–

Complexity analysis

Approach	Time	Space	When to Use
Graph Based Shortest Path	O(V * E)	O(V + E)	When modeling the problem directly as a graph and computing paths per character
Dynamic Programming with Floyd-Warshall	O(26^3)	O(26^2)	Best when the alphabet size is small and fixed
Graph + Dijkstra	O(26 * (E log V))	O(V + E)	Useful when transformation rules form a larger weighted graph
Floyd-Warshall All-Pairs Shortest Path	O(26^3)	O(26^2)	Optimal interview solution due to constant alphabet size

Frequently asked questions

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

Minimum Cost to Convert String I solution and explanation

The problem

Approach overview

Approach 1: Graph Based Shortest Path Approach

Approach 2: Dynamic Programming with Floyd-Warshall

Approach 3: Graph-based Approach with Dijkstra's Algorithm

Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path

Approach 5: Floyd Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Cost to Convert String I solution and explanation

The problem

Approach overview

Approach 1: Graph Based Shortest Path Approach

Approach 2: Dynamic Programming with Floyd-Warshall

Approach 3: Graph-based Approach with Dijkstra's Algorithm

Approach 4: Floyd-Warshall Algorithm for All-Pairs Shortest Path

Approach 5: Floyd Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems