Permutation in String Leetcode Solution
Permutation in String Leetcode Problem :
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.
Permutation in String Leetcode Solution :
Constraints :
- 1 <= s1.length, s2.length <= 10^4
- s1 and s2 consist of lowercase English letters.
Example 1:
- Input: s1 = “ab”, s2 = “eidboaoo”
- Output: false
Approach :
The alphabets in a permutation that is to be searched will always be the same, and so will their count.
The thing that counts in s2 is that each substring has the same number of characters as in s1. As a result, we make a hashmap that contains the count of each character in the string s1. After that, we slide a window over the string s2 and lower the number for characters that appear in the window. When all of the counters in the hashmap reach 0, we’ve found the permutation.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution { public: bool checkInclusion(string s1, string s2) { if (s1.size() > s2.size()) return false; vector< int> s1v (26, 0); for (auto c : s1) s1v[c - 'a']++; vector< int> s2v (26, 0); int l = 0, r = 0; while (r < s2.size()) { s2v[s2[r]-'a']++; if (r - l + 1 == s1.size()) if (s1v == s2v) return true; if (r - l + 1 < s1.size()) r++; else { s2v[s2[l]-'a']--; l++; r++; } } return false; } };
class Solution { public boolean checkInclusion(String s1, String s2) { if(s1.length() >s2.length())return false; int[] data = new int[26]; int[] test = new int[26]; for(char c : s1.toCharArray())data[c-'a']++; for(int i=0;i< s1.length();i++)test[s2.charAt(i)-'a']++; int n=s1.length(); for(int i=0;i< s2.length()-n;i++){ if(equalsString(test, data))return true; test[s2.charAt(i+n)-'a']++; test[s2.charAt(i)-'a']--; } return equalsString(test, data); } private boolean equalsString(int[] s1, int[] s2){ for(int i=0;i< 26;i++) if(s1[i]!=s2[i])return false; return true; } }
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: checker = ''.join(sorted(s1)) for i in range(len(s2) - len(s1)+1): temp = ''.join(sorted(s2[i:i+len(s1)])) if temp == checker: return True return False
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment