LeetCode 2976 – Minimum Cost to Convert String I |Java Solution

Описание: 📂 Source Code:
https://github.com/RakeshMundel/LeetCode-P...

🔥 LeetCode POTD 2976 – Minimum Cost to Convert String I | Java Solution

In this video, we solve LeetCode Problem 2976: Minimum Cost to Convert String I using the Floyd–Warshall algorithm (All-Pairs Shortest Path).

🧠 Problem Overview

🔹 You are given two strings source and target of equal length
🔹 You are also given character mappings original → changed with associated costs
🔹 In one operation, you may change a character if a corresponding rule exists
🔹 Multiple transformations can be chained together

🔹 Your goal is to compute the minimum total cost to convert source into target
🔹 If any character cannot be converted, return -1

💡 Key Insight

Each character (a–z) can be treated as a node in a graph, and every conversion rule becomes a directed weighted edge.

Since:

There are only 26 characters

We may need multi-step conversions

We can apply Floyd–Warshall to precompute the minimum cost between every pair of characters.

After that:

For each position i, simply add the cost of converting source[i] → target[i]

If any conversion is impossible, return -1

🚀 Approach Used
Build a 26 × 26 cost matrix
Initialize direct conversions with minimum costs
Run Floyd–Warshall to compute all-pairs shortest paths
Traverse both strings and accumulate conversion costs
Return -1 if any character mapping is unreachable

⏱️ Time & Space Complexity
Time Complexity: O(26³ + n) ≈ O(n)
Space Complexity: O(26²)
(n = length of the string)

📌 Perfect for:
Graph algorithms on small alphabets
Floyd–Warshall practice
String transformation problems
LeetCode POTD & interview preparation

#LeetCode #LeetCode2976 #POTD #Graphs #FloydWarshall #ShortestPath #Strings #DSA #CodingInterview #Java #FAANG #CareerYacht