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 findAnagrams(string s, string p) {
vector result;
if(s.size()<p.size()) return result;
unordered_map freq_p,freq_window;
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 List findAnagrams(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:
    vector findAnagrams(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 IList FindAnagrams(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; 
}