LeetCode 2977 | Minimum Cost to Convert String II | Java | Hard | Floyd-Warshall & D P | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 2977 — Minimum Cost to Convert String II using Graph All-Pairs Shortest Paths & Dynamic Programming in Java.
We are given two strings, source and target, along with a collection of string replacement operations and costs. Unlike the first variant where single characters were changed independently, here we can replace multi-character substrings, provided any two chosen operations are either completely disjoint or cover the exact identical range of indices. This constraint implies that the global transformation breaks down into partitioning the string into non-overlapping segments, where each segment is either left unchanged or converted via a multi-hop sequence of substring operations of equal length.
We model all unique substring tokens across original and changed arrays as vertices in a directed graph. Because there are at most 100 conversion rules, the number of unique strings is at most 200, allowing us to compute all-pairs shortest paths using the Floyd-Warshall algorithm with sparsity pruning in just a few milliseconds. We then apply 1D Dynamic Programming across the length of the string, testing single-character matches and checking transitions against only the distinct substring lengths present in the original rules.
🔥 Problem Highlights
✅ Any pair of operations must have either disjoint or identical index ranges
✅ Substring conversions chain together as shortest paths on identical intervals
✅ Graph has at most 200 unique vertices, making Floyd-Warshall optimal
✅ Sparsity check prunes unreachable nodes in Floyd-Warshall for rapid execution
✅ 1D Dynamic Programming tests only distinct lengths present in the input rules
✅ Time Complexity: O(V^3 + N * |lengths| * L_max) | Auxiliary Space: O(V^2 + N)
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding
01:55 Key Observation
03:07 Floyd-Warshall & 1D DP Approach
04:37 Java Code Walkthrough
05:49 Execution & Test Cases
07:04 Time Complexity Analysis
07:58 Space Complexity Analysis
08:45 Outro & Wrap-up
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Graph Shortest Path
Floyd-Warshall Algorithm
1D Dynamic Programming
Interval Partitioning
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does the constraint 'operations must be either disjoint or identical' enable a 1D DP solution?
1️⃣ It ensures characters can only be deleted and never inserted
2️⃣ It prevents partially overlapping interval dependencies, guaranteeing that every segment of the string can be partitioned and transformed independently
3️⃣ It forces the string length to be a multiple of the substring length
4️⃣ It guarantees that all edge weights in the graph are 1
#LeetCode2977 #LeetCode #MinimumCostToConvertStringII #Java #JavaDSA #FloydWarshall #DynamicProgramming #Graph #ShortestPath #String #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 2977 — Minimum Cost to Convert String II using Graph All-Pairs Shortest Paths & Dynamic Programming in Java.
We are given two strings, source and target, along with a collection of string replacement operations and costs. Unlike the first variant where single characters were changed independently, here we can replace multi-character substrings, provided any two chosen operations are either completely disjoint or cover the exact identical range of indices. This constraint implies that the global transformation breaks down into partitioning the string into non-overlapping segments, where each segment is either left unchanged or converted via a multi-hop sequence of substring operations of equal length.
We model all unique substring tokens across original and changed arrays as vertices in a directed graph. Because there are at most 100 conversion rules, the number of unique strings is at most 200, allowing us to compute all-pairs shortest paths using the Floyd-Warshall algorithm with sparsity pruning in just a few milliseconds. We then apply 1D Dynamic Programming across the length of the string, testing single-character matches and checking transitions against only the distinct substring lengths present in the original rules.
🔥 Problem Highlights
✅ Any pair of operations must have either disjoint or identical index ranges
✅ Substring conversions chain together as shortest paths on identical intervals
✅ Graph has at most 200 unique vertices, making Floyd-Warshall optimal
✅ Sparsity check prunes unreachable nodes in Floyd-Warshall for rapid execution
✅ 1D Dynamic Programming tests only distinct lengths present in the input rules
✅ Time Complexity: O(V^3 + N * |lengths| * L_max) | Auxiliary Space: O(V^2 + N)
⏱️ TIMESTAMPS
00:00 Intro
00:55 Problem Understanding
01:55 Key Observation
03:07 Floyd-Warshall & 1D DP Approach
04:37 Java Code Walkthrough
05:49 Execution & Test Cases
07:04 Time Complexity Analysis
07:58 Space Complexity Analysis
08:45 Outro & Wrap-up
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/30-January/2977-Minimum-Cost-to-Convert-String-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Graph Shortest Path
Floyd-Warshall Algorithm
1D Dynamic Programming
Interval Partitioning
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does the constraint 'operations must be either disjoint or identical' enable a 1D DP solution?
1️⃣ It ensures characters can only be deleted and never inserted
2️⃣ It prevents partially overlapping interval dependencies, guaranteeing that every segment of the string can be partitioned and transformed independently
3️⃣ It forces the string length to be a multiple of the substring length
4️⃣ It guarantees that all edge weights in the graph are 1
#LeetCode2977 #LeetCode #MinimumCostToConvertStringII #Java #JavaDSA #FloydWarshall #DynamicProgramming #Graph #ShortestPath #String #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description