Minimum Time to Revert Word to Initial State | Part I | Part II | KMP | Leetcode 3029 | 3031
94Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 39th Video of our Playlist "Strings : Popular Interview Problems".
In this video we will try to solve two very good string problems asked in Leetcode Weekly Contest 383 :
Minimum Time to Revert Word to Initial State I (Leetcode 3029)
Minimum Time to Revert Word to Initial State II (Leetcode 3031)
KMP Detailed - https://youtu.be/qases-9gOpk?si=G2XukMW4hRqtU6pr
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 Time to Revert Word to Initial State I | Minimum Time to Revert Word to Initial State II | Leetcode 3029 | 3031
Company Tags : Will update soon
My solutions on Github(C++ & JAVA) :
Part I : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Minimum%20Time%20to%20Revert%20Word%20to%20Initial%20State%20I.cpp
Part II : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Minimum%20Time%20to%20Revert%20Word%20to%20Initial%20State%20II.cpp
Leetcode Link :
Part I : https://leetcode.com/problems/minimum-time-to-revert-word-to-initial-state-i/description/
Part II : https://leetcode.com/problems/minimum-time-to-revert-word-to-initial-state-ii/description/
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach - 1 Summary : The goal is to determine the minimum number of iterations required to reach the initial state by repeatedly concatenating substrings of length 'k' from the end of the word to the beginning. The method utilizes a helper function 'check' to verify if the substring from index 'i' to 'n' is equal to the substring from index '0' to 'n - i.' The algorithm iterates through the word, incrementing a counter 'count' and updating the index 'i' by 'k' until a match is found, and then returns the final count.
Approach-2 Summary : This method calculates the minimum number of iterations needed to reach the initial state by repeatedly concatenating substrings of length 'k' from the end of the word to the beginning. The algorithm utilizes the Knuth-Morris-Pratt (KMP) algorithm's Longest Prefix Suffix (LPS) function to find the length of the longest proper prefix which is also a suffix. The code initializes an LPS array, finds the maximum LPS value, and then iterates through a loop to determine if a valid substring length 'k' exists based on the LPS array. Finally, the method returns the minimum number of iterations required.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ 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 #2024 #newyear