Find all Anagrams in a String Leetcode Solution
Find All Anagrams in a String Leetcode Problem :
Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example :
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Find All Anagrams in a String Leetcode Solution :
Constraints :
- 1 <= s.length, p.length <= 3 * 104
- s and p consist of lowercase English letters.
Example 1:
- Input: s = “abab”, p = “ab”
- Output: [0,1,2]
- Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.
Intuition :
- whenever all characters of p string matches with s string’s certain window
save the leftmost position of the window. - do this operation until the end of the string s
So clearly we need to count the frequency of
- p string
- s string’s current window (which is equal to length of p).
Approach :
- create two arrays s_cout, p_count of size 26 and intialise it to zero.
- create an array to store the final answer ans
- corner case: a. if s size is empty or lesser than p
- count the frequecies of s, p until the size of p (this is nothing but our first sliding window.)
- if s_count matches with the p_count store the leftmost index of the array, here in this case is starting positon.
- we already travesed 0 to p.size()-1, so we are travesing p.size() to s.size() of string s
- count the next character of s
- and remove the leftmost character of the sliding window from count array of s. (nothing but we are maintaining the current sliding window.)
- check whether current sliding count matches with p_count, if yes store the result.
- return ans.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
vector findAnagrams(string s, string p) {
vector< int> s_count(26,0), p_count(26,0);
vector< int> ans;
if(s.size() < p.size()) return ans;
for(int i =0; i< p.size(); i++){
s_count[s[i] -'a']++;
p_count[p[i]- 'a']++;
}
if(s_count == p_count) ans.push_back(0);
for(int i = p.size(); i< s.size(); i++){
/* To maintain the current sliding window, here we are adding the next character to
* our slidng window and removing the left most character from sliding window.
*/
s_count[s[i] -'a']++;
s_count[s[i- p.size()]-'a']--;
if(s_count == p_count) ans.push_back(i-p.size()+1);
}
return ans;
}
};
Java
class Solution {
public List findAnagrams(String s, String p) {
List result = new ArrayList();
int[] char_counts = new int[26];
for(char c: p.toCharArray()) {
char_counts[c-'a']++;
}
int left = 0;
int right = 0;
int count = p.length();
while(right < s.length()) {
if(char_counts[s.charAt(right++)-'a']-- >= 1) count--;
if(count == 0) result.add(left);
if(right-left==p.length() && char_counts[s.charAt(left++)-'a']++ >= 0) count++;
}
return result;
}
}
Python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
res = []
hashmap = collections.Counter(p)
left = 0
right = 0
count = len(p)
while right < len(s):
if hashmap[s[right]] >= 1:
count -= 1
hashmap[s[right]] -= 1
right += 1
if count == 0:
res.append(left)
if right-left==len(p):
if hashmap[s[left]] >= 0:
count += 1
hashmap[s[left]] += 1
left += 1
return res
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