Problem
TC:O(n)
SC:(k) is no. of substrings(anagrams) + O(1) for using constant space array of size 26
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> map = new HashMap<>();
int arrp[] = new int[26];
for(int i = 0;i<p.length();i++) arrp[p.charAt(i)-'a']++;
int arrs[] = new int[26];
List<Integer> result = new ArrayList<>();
int left =0,right = 0;
while(right<s.length()){
if(right-left+1< p.length()){
arrs[s.charAt(right)-'a']++;
right++;
}
else{
arrs[s.charAt(right)-'a']++;
right++;
if(check(arrp,arrs)) result.add(left);
arrs[s.charAt(left)-'a']--;
left++;
}
}
return result;
}
public boolean check(int a[], int b[]){
for(int i =0;i<26;i++){
if(a[i]!=b[i]) return false;
}
return true;
}
}
Top comments (0)