hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Find All Anagrams in a String
Problem : 438. Find All Anagrams in a String
Problem Link : https://leetcode.com/problems/find-all-anagrams-in-a-string/
Companies Asked : Uber, Adobe, Yahoo, Facebook, Apple, Oracle, Amazon, Google, Microsoft, Bloomberg, ByteDance [ Retrieved Using LeetCode Which Company extension ]
Approach:
The problem is said to find the string, s1 into the string, s2, where all the characters may be permuted.
When it says permuted and the length could be 3*10^4, it simply illustrates that we need to work the character frequencies.
In a substring of s1, of length |s2|, we need to make sure that we have all the characters of s1.
We will declare two pointer left and right.
the right pointer will move forward with taking the current character while the left pointer will move only if the right is failed to encounter a character that is inappropriate with respect to s1.
Now the inappropriateness is possible in two ways -
If the current character does not exist in the s1.
In this case, we will reset both the left and right pointers. We will start afresh.
Or, if the current character appears more than the required appearance we have encountered in s1.
In this case, we will reduce the appearance of the current character of s2 by increasing the left pointer once.
In every move, we will check if the difference between the left and the right pointer is off s2 length.
If we can find such a substring enter the left pointer into the answer list.
Keep doing the same until the right pointer the end of s1.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(logn)
Code [C++]
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>originalFreq(26, 0), duplicateFreq(26, 0);
int s1Len = s1.size();
int s2Len = s2.size();
if(s1Len > s2Len) return {};
for(int i=0; i<s1Len; i++){
originalFreq[s1[i] - 'a']++;
duplicateFreq[s1[i] - 'a']++;
}
vector<int>ans;
int left = 0, right = 0, tLen = 0;
while(right<s2Len && left <= right){
if(duplicateFreq[s2[right]-'a'] > 0){
duplicateFreq[s2[right]-'a']--;
right++;
tLen++;
}
else{
if((right - left) == s1Len){ans.push_back(left);}
if(left < right && originalFreq[s2[left]-'a'] > 0){
duplicateFreq[s2[left]-'a']++;
left++; tLen--;
}
else{
tLen = 0;
right++;
left = right;
}
}
}
if((right - left) == s1Len && tLen == s1Len) {ans.push_back(left);}
return ans;
}
};