/**
* 438. Find All Anagrams in a String
* Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
* Strings consists of lowercase English letters only and the length of
* both strings s and p will not be larger than 20,100.
* The order of output does not matter.
* Example 1:
* 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”.
* See another anagrams question in GroupAnagrams
*/
See my solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/amazon/medium/AnagramsInAString.java
Anagram by definition is when two string have the same frequency for characters, for example abc , bca, cba are all anagrams of each other.
The problem can be solved via creating an array of source and target characters and comparing the two arrays for equality. You iterate the source array from left to right while using a sliding window approach, at each increment you compare the source and target arrays, if equal there is an anagram match.
Instead of arrays, the same could be done using maps but adding , removing and comparison in maps is a lot more computationally expensive.
Here is the code:
public List<Integer> findAnagrams(String s, String p) {
if (s.isEmpty() || p.isEmpty() || p.length() > s.length()) return new ArrayList();
int[] target = new int[26];
int[] source = new int[26];
List<Integer> out = new ArrayList<>();
//initialize source and target arrays
for (int i = 0; i < p.length(); i++) {
char c = p.charAt(i);
target[c - 'a'] += 1;
}
for (int i = 0; i < p.length(); i++) {
char c = s.charAt(i);
source[c - 'a'] += 1;
}
if (Arrays.equals(target, source)) {
out.add(0);
}
int len = p.length();
//use a sliding window approach to determine whether source matches target
for (int i = 1; (i + len) <= s.length(); i++) {
char c = s.charAt(i - 1);
source[c - 'a'] -= 1; //decrement char at prior index
c = s.charAt(i + len - 1);
source[c - 'a'] += 1; //increment char at new index
if (Arrays.equals(target, source)) {
out.add(i); //if source and target match then add starting index to output
}
}
return out;
}