Permutation in String | Multiple Approaches | Clean Dry Run | Leetcode 567 | codestorywithMIK

Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A This is the 27th Video of our Playlist "Sliding Window : Popular Interview Problems" by codestorywithMIK In this video we will try to solve a classic Sliding Window Problem : Permutation in String | Multiple Approaches | Clean Dry Run | Leetcode 567 | codestorywithMIK Permutation Video Link - https://www.youtube.com/watch?v=T8hqjK94Fig 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 : Permutation in String | Multiple Approaches | Clean Dry Run | Leetcode 567 | codestorywithMIK Company Tags : Amazon, Microsoft My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Sliding%20Window/Permutation%20in%20String.cpp Leetcode Link : https://leetcode.com/problems/permutation-in-string My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo Instagram : https://www.instagram.com/codestorywithmik/ Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/ Twitter : https://twitter.com/CSwithMIK Subscribe to my channel : https://www.youtube.com/@codestorywithMIK ╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗ ║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣ ╠╗║╚╝║║╠╗║╚╣║║║║║═╣ ╚═╩══╩═╩═╩═╩╝╚╩═╩═╝ Summary : Approach 1: Brute Force - TLE Time Complexity: O(n!⋅m) Space Complexity: O(n) Description: This approach generates all permutations of the string s1 using recursion. For each permutation, it checks if that permutation exists as a substring in s2 using the find method. The function recursively swaps characters to create permutations and performs early exits if a valid permutation is found. Limitations: This method is inefficient for longer strings due to the factorial growth of permutations, leading to a Time Limit Exceeded (TLE) error for larger inputs. Approach 2: Sorting and Comparing - ACCEPTED Time Complexity: O((m−n)⋅nlogn) Space Complexity: O(n) Description: This approach first sorts the string s1. It then iterates through each substring of s2 that has the same length as s1, sorts that substring, and checks if it matches the sorted version of s1. The comparison relies on the fact that permutations of the same characters will result in identical sorted strings. Advantages: This method is more efficient than the brute force approach but still incurs a logarithmic cost due to sorting. Approach 3: Sliding Window - ACCEPTED Time Complexity: O(m+n) Space Complexity: O(26) (constant space for frequency counts) Description: This efficient approach uses frequency arrays (or vectors) to keep track of the count of characters in s1 and the current window of characters in s2. As it slides a window of length n over s2, it updates the frequency count dynamically, adding a new character and removing the leftmost character as the window shifts. It checks for matches between the frequency counts of s1 and the current window in s2. Advantages: This method is optimal with linear time complexity, making it suitable for large input sizes, and effectively avoids the need for sorting or generating permutations. ✨ 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 #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik