Minimum Cost to Convert String I | LeetCode 2976 | Graph + Floyd Warshall Explained

In this video, we solve LeetCode 2976: Minimum Cost to Convert String I. Code: https://leetcode.com/problems/minimum-cost-to-convert-string-i/solutions/7533013/floyd-warshall-algorithm-in-detail-simpl-ri77 Upsolve Leetcode Contest: https://youtube.com/playlist?list=PLsLlEdtakGoxoGbAwVRSlRjuB1yv1ycnc&si=_IDShX4wq0BxIkNf Greedy & Heaps: https://youtube.com/playlist?list=PLsLlEdtakGozAWFrLtFyKfzHL69QMdpkK&si=05iZsUB_hCmYZGPN Two pointers: https://youtube.com/playlist?list=PLsLlEdtakGow7Brk6c1OM_Bh-Mz55V7nX&si=hwShAQg6AT_VlwOm Sliding Window: https://youtube.com/playlist?list=PLsLlEdtakGozlKx_L-5PQJO-ua_maQb6R&si=hNoGQVZUI7OR9poU Maths & Geometry: https://youtube.com/playlist?list=PLsLlEdtakGoyWTBlOMC_mQ8Pv1M_pY2MX&si=MHwHo53uuirf26zC Stack: https://youtube.com/playlist?list=PLsLlEdtakGowhIcIi8uvWRy7Zw-bKoD85&si=9jvT_g2NQHFUHAMg Set & Map: https://youtube.com/playlist?list=PLsLlEdtakGozffR58V-u_qpYkwkR2Nc_F&si=_h2GBLEVi-hQyvI- Bit manipulation: https://youtube.com/playlist?list=PLsLlEdtakGowS_aAEQDNtNJA9zWkyk5uf&si=f0yO3hkGsorAhiod Backtracking: https://youtube.com/playlist?list=PLsLlEdtakGox7HMCBg3_sh8TrZoKnTPep&si=CMvDSFGzMRg6io1Y Linked List: https://youtube.com/playlist?list=PLsLlEdtakGowLdcT3ocFdt5MCEuTYVOzF&si=16QNR2HY_bLvVw2n Binary Search: https://youtube.com/playlist?list=PLsLlEdtakGozNxx5rfRgEW-1DYseLnDbV&si=RZ1BUYmSAvIvi5a5 Graph: https://youtube.com/playlist?list=PLsLlEdtakGox1mdnH0PrJUhHJByUstkvx&si=JW-6qPw7zXDH-29j Dynamic Progamming: https://youtube.com/playlist?list=PLsLlEdtakGoyNROP7uWS9OLLHs9_JluVM&si=vJY6SxVXIHAbgzgk 🔹 Problem Summary: You are given two strings source and target of equal length. You are also given transformation rules where a character can be changed to another character with a given cost. You can apply these operations any number of times. Your task is to find the minimum total cost to convert source into target. If it is not possible to convert, return -1. 🔹 Key Observation: Each character conversion is independent, but conversions can be chained. This naturally forms a directed weighted graph of characters (a → b with cost). 🔹 Approach Used: 1️⃣ Graph Construction - Each lowercase character (a–z) is treated as a node. - Each conversion rule forms a directed weighted edge. 2️⃣ Floyd–Warshall Algorithm - Since we need the minimum cost between all pairs of characters, we apply Floyd–Warshall on a 26×26 matrix. - This precomputes the minimum cost to convert any character to any other. 3️⃣ Final Cost Calculation - Traverse each index i: - If source[i] == target[i], cost = 0. - Otherwise, add the precomputed shortest path cost. - If any conversion is impossible, return -1. 🔹 Time & Space Complexity: - Time Complexity: O(26³ + n) - Space Complexity: O(26²) This problem is a perfect example of applying all-pairs shortest path on a small fixed graph. #LeetCode2976 #MinimumCostToConvertString #FloydWarshall #GraphAlgorithms #ShortestPath #AllPairsShortestPath #LeetCodeDaily #MediumLeetCode #GraphDP #StringProblems #CharacterTransformation #WeightedGraph #AlgorithmExplanation #FAANGPreparation #InterviewProblems #CompetitiveProgramming #StudyPlacement #LeetCodeStrings #GraphTheory