Solution:
Time complexity: in O(n)
import java.util.*;
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new LinkedList<>();
int n=s.length();
HashMap<Character,Integer> s_mp=new HashMap<>();
HashMap<Character,Integer> p_mp=new HashMap<>();
for(int i=0;i<p.length();i++)
{
char c=p.charAt(i);
p_mp.put(c,p_mp.getOrDefault(c,0)+1);
}
int i=0; int j=0;
while(j<n)
{
char cs=s.charAt(j);
s_mp.put(cs,s_mp.getOrDefault(cs,0)+1);
if(j-i+1==p.length())
{
if(s_mp.equals(p_mp))
{
result.add(i);
}
// Remove the character that's left behind as the window slides
char leftChar = s.charAt(i);
if (s_mp.get(leftChar) == 1) s_mp.remove(leftChar);
else s_mp.put(leftChar, s_mp.get(leftChar) - 1);
i+=1;
}
j+=1;
}
return result;
}
}
No comments:
Post a Comment