Permutation in String | Multiple Approaches | Clean Dry Run | Leetcode 567 | codestorywithMIK
446Whatsapp 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 - • Permutations | INTUITIVE | Backtracki...
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 Window/Permutation in String.cpp
Leetcode Link : https://leetcode.com/problems/permutation-in-string
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
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 : / @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