Minimum Cost to Convert String I | Weekly Contest 377 | 2 Approaches | Leetcode 2976

Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 42nd Video of our Playlist "Graphs : Popular Interview Problems".
In this video we will try to solve a very good problem on application of Shortest Path Graph Algorithms (Floyd Warshall & Dijkstra's) - Minimum Cost to Convert String I (Leetcode 2976).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Minimum Cost to Convert String I
Company Tags : will update soon
My solutions on Github(C++ & JAVA) :
Floyd Warshall - https://github.com/MAZHARMIK/Intervie...
Dijkstra's Algo - https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/minimum...

My DP Concepts Playlist :    • Roadmap for DP | How to Start DP ? | ...  
My Graph Concepts Playlist :    • Graph Concepts & Qns - 1 : Graph will...  
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Subscribe to my channel :    / @codestorywithmik  
Instagram :   / codestorywithmik  
Facebook :   / 100090524295846  
Twitter :   / cswithmik  


Approach-1 Summary(Floyd Warshall) : The FloydWarshall function initializes 2D vector distances to represent the minimum costs between characters. It then iterates through the character replacements, updating the corresponding distances in the matrix. Subsequently, it applies the Floyd-Warshall algorithm to compute the shortest paths between all pairs of characters. The minimumCost function utilizes the distances computed by FloydWarshall to find the minimum cost of transforming the source string into the target string based on the specified character replacements. It iterates through each character position, accumulating the costs of necessary replacements. If there is no valid transformation for a character pair, it returns -1. Otherwise, it returns the total minimum cost of the transformation.

Approach-2 Summary : The dijkstra function implements Dijkstra's algorithm to compute the shortest paths from a given source character to all other characters in the graph represented by an adjacency list. It uses a priority queue to select the next node with the smallest distance and updates the distances accordingly. The minimumCost function utilizes the adjacency list constructed from the character replacements to find the minimum cost of transforming the source string into the target string. It applies Dijkstra's algorithm for each unique character in the original vector, updating the distances matrix. Then, it iterates through each character position, accumulating the costs of necessary replacements. If there is no valid transformation for a character pair, it returns -1. Otherwise, it returns the total minimum cost of the transformation.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa