# Solution For Find All Anagrams In A String

Problem Statement:

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”.

Example 2:

Input:

s: “abab” p: “ab”

Output:

[0, 1, 2]
Explanation:

The substring with start index = 0 is “ab”, which is an anagram of “ab”.

The substring with start index = 1 is “ba”, which is an anagram of “ab”.

The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Solution:

The problem can be solved using the sliding window technique, which involves using two pointers to create a window of characters in the given string. We will create two hash maps, one to store the frequencies of characters in the pattern string and the other to store the frequencies of characters in the current window of the string. We will iterate through the string and for each character, we will increment its count in the second hash map. We will also decrement the count of the character at the left end of the window and remove it if its frequency becomes zero.

At each iteration, we will check if the current window is an anagram of the pattern string. If yes, we will add the starting index of the window to the result array. We will continue this process until the right pointer reaches the end of the string.

Code:

class Solution {

public:

vector

vector

if(s.size()<p.size()) return result;

unordered_map

for(int i=0;i<p.size();i++){

freq_p[p[i]]++;

freq_window[s[i]]++;

}

int left=0,right=p.size()-1;

while(right<s.size()){

if(freq_p==freq_window) result.push_back(left);

freq_window[s[left]]–;

if(freq_window[s[left]]==0) freq_window.erase(s[left]);

left++;

if(right+1<s.size()) freq_window[s[++right]]++;

}

return result;

}

};

Time Complexity: O(n) where n is the length of the string s

Space Complexity: O(k) where k is the size of the alphabet (26 for lowercase English letters)

## Step by Step Implementation For Find All Anagrams In A String

public ListfindAnagrams(String s, String p) { List list = new ArrayList<>(); if (s == null || s.length() == 0 || p == null || p.length() == 0) return list; int[] hash = new int[256]; //record each character in p for (char c : p.toCharArray()) { hash[c]++; } //two points, initialize count to p's length int left = 0, right = 0, count = p.length(); while (right < s.length()) { //move right everytime, if the character exists in p's hash, decrease the count //current hash value >= 1 means the character is existing in p if (hash[s.charAt(right++)]-- >= 1) count--; //when the count is down to 0, means we found the right anagram //then add window's left to result list if (count == 0) list.add(left); //if we find the window's size equals to p, then we have to move left (narrow the window) so we could find the new match window //if the character in the left side exists in p's hash, we increase the count if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++; } return list; }

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: # Initialize a list to store the indices of all possible anagrams output = [] # If the length of the input string is less than the length of the anagram, there can be no anagrams if len(s) < len(p): return output # Initialize two dictionaries to keep track of the number of each character in the input string and anagram p_dict = {} s_dict = {} # Iterate through the anagram and store the number of each character in the anagram dictionary for char in p: if char in p_dict: p_dict[char] += 1 else: p_dict[char] = 1 # Iterate through the first len(p) characters of the input string and store the number of each character in the input string dictionary for i in range(len(p)): char = s[i] if char in s_dict: s_dict[char] += 1 else: s_dict[char] = 1 # If the dictionaries are equal, the indices of the first len(p) characters form an anagram if s_dict == p_dict: output.append(0) # Iterate through the rest of the input string, removing the first character and adding the next character # Check if the updated dictionaries are equal # If they are equal, the indices of the len(p) characters form an anagram for i in range(len(p), len(s)): # Remove the first character from the dictionary first_char = s[i-len(p)] s_dict[first_char] -= 1 if s_dict[first_char] == 0: del s_dict[first_char] # Add the next character to the dictionary next_char = s[i] if next_char in s_dict: s_dict[next_char] += 1 else: s_dict[next_char] = 1 # If the dictionaries are equal, the indices of the len(p) characters form an anagram if s_dict == p_dict: output.append(i-len(p)+1) return output

//Solution: /** * @param {string} s * @param {string} p * @return {number[]} */ var findAnagrams = function(s, p) { //Create a hashmap to store the counts of each character in string p let map = {}; for(let i = 0; i < p.length; i++){ if(!(p[i] in map)){ map[p[i]] = 1; } else{ map[p[i]]++; } } //Create an array to store the indices of the anagrams let anagrams = []; //Two pointers, left and right, to keep track of the current window let left = 0; let right = 0; //Create a counter variable to keep track of the number of characters left to match let counter = p.length; //Loop through the string s while(right < s.length){ //If the character at index right is in the hashmap, decrement the count if(s[right] in map){ map[s[right]]--; //If the count is now 0, that means we have found a match, so decrement the counter if(map[s[right]] === 0){ counter--; } } right++; //If the counter is 0, that means we have found all the characters in p, so add the left pointer to the anagrams array if(counter === 0){ anagrams.push(left); } //If the right pointer - left pointer is equal to p.length, that means we have reached the end of the current window, so we need to move the left pointer if(right - left === p.length){ //If the character at index left is in the hashmap, increment the count if(s[left] in map){ map[s[left]]++; //If the count is now greater than 0, that means we have found a character that does not match, so increment the counter if(map[s[left]] > 0){ counter++; } } left++; } } return anagrams; };

class Solution { public: vectorfindAnagrams(string s, string p) { vector res; if (s.empty() || p.empty()) return res; int n = s.size(), m = p.size(); vector cnts(26); for (char c : p) ++cnts[c - 'a']; vector curCnts(26); for (int i = 0; i < n; ++i) { ++curCnts[s[i] - 'a']; if (i >= m) --curCnts[s[i - m] - 'a']; if (curCnts == cnts) res.push_back(i - m + 1); } return res; } };

public IListFindAnagrams(string s, string p) { // create a list to store all the starting indices // of p's anagrams in s List result = new List (); // create an array to store the count of // each character in p int[] pCount = new int[26]; int[] sCount = new int[26]; // store the count of each character of p for (int i = 0; i < p.Length; i++) pCount[p[i] - 'a']++; // iterate through s and store the count // of each character in sCount array for (int i = 0; i < s.Length; i++) { // if i lies outside the range of p // then reduce the count of first // character of previous window if (i >= p.Length) sCount[s[i - p.Length] - 'a']--; // add the count of current character sCount[s[i] - 'a']++; // compare arrays if (compare(pCount, sCount)) result.Add(i - p.Length + 1); } return result; } // compare two arrays public bool compare(int[] arr1, int[] arr2) { for (int i = 0; i < 26; i++) if (arr1[i] != arr2[i]) return false; return true; }