public List<Integer> findAnagrams(String s, String p){ List<Integer> ans = new ArrayList<>(); int pLen = p.length(); int sLen = s.length(); if (pLen > sLen) { return ans; }
Map<Character, Integer> patMap = new HashMap<>(); for (char ch : p.toCharArray()) { patMap.put(ch, patMap.getOrDefault(ch, 0) + 1); }
int left = 0; int right = left + pLen;
// Sliding Window Map<Character, Integer> winMap = new HashMap<>(); for (int i = left; i < right; i++) { char ch = s.charAt(i); winMap.put(ch, winMap.getOrDefault(ch, 0) + 1); }
if (patMap.equals(winMap)) { ans.add(left); }
while (right < sLen) { char chLeft = s.charAt(left); winMap.put(chLeft, winMap.get(chLeft) - 1); if (winMap.get(chLeft) == 0) { winMap.remove(chLeft); }
public List<Integer> findAnagrams(String s, String p){ List<Integer> ans = new ArrayList<>(); int pLen = p.length(); int sLen = s.length(); if (pLen > sLen) { return ans; }
for (int i = 0; i < pLen; i++) { pCnt[p.charAt(i) - 'a']++; wCnt[s.charAt(i) - 'a']++; }
if (check(pCnt, wCnt)) { ans.add(0); }
for (int i = 0; i < sLen - pLen; i++) { // minus left wCnt[s.charAt(i) - 'a']--; // plus right wCnt[s.charAt(i + pLen) - 'a']++; if (check(pCnt, wCnt)) { ans.add(i + 1); } }
return ans; }
publicstaticbooleancheck(int[] pCnt, int[] wCnt){ for (int i = 0; i < 26; i++) { if (pCnt[i] != wCnt[i]) { returnfalse; } }
public List<Integer> findAnagrams(String s, String p){ List<Integer> ans = new ArrayList<>(); int pLen = p.length(); int sLen = s.length(); if (pLen > sLen) { return ans; }
int[] count = newint[26];
for (int i = 0; i < pLen; i++) { count[s.charAt(i) - 'a']++; count[p.charAt(i) - 'a']--; }
// different chars int diff = 0; for (int x : count) { if (x != 0) { diff++; } }
if (diff == 0) { ans.add(0); }
for (int i = 0; i < sLen - pLen; i++) { char leftCh = s.charAt(i); if (count[leftCh - 'a'] == 1) { diff--; // s has leftCh, p not, diff-- } elseif (count[leftCh - 'a'] == 0) { diff++; // both s and p has leftCh, means move right, will not equal } count[leftCh - 'a']--;
char rightCh = s.charAt(i + pLen); if (count[rightCh - 'a'] == -1) { diff--; // p hash rightCh, s not, that means win will equal } elseif (count[rightCh - 'a'] == 0) { diff++; // both s and p has rightCh, means move right, will not equal } count[rightCh - 'a']++;