Last updated on July 18th, 2024 at 10:20 pm

Here, We see Find All Anagrams in a String LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Hash Table

Companies

Amazon

Level of Question

Medium

Find All Anagrams in a String LeetCode Solution

Problem Statement

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

1. Find All Anagrams in a String LeetCode Solution C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> goal(26), cur(26), res;
        for(char c : p) goal[c - 'a']++;
        for(int i = 0; i < s.size(); i++) {
            cur[s[i] - 'a']++;
            if(i >= p.size()) cur[s[i - p.size()] - 'a']--;
            if(cur == goal) res.push_back(i - p.size() + 1);
        }
        return res;
    }
};

2. Find All Anagrams in a String LeetCode Solution Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
    int freq1[] = new int[26];
    int freq2[] = new int[26];
        List<Integer> list = new ArrayList<>();
        
        if(s.length()<p.length())
            return list;
        
        for(int i=0; i<p.length(); i++){
            freq1[s.charAt(i)-'a']++;
            freq2[p.charAt(i)-'a']++;
        }
    
        int start=0;
        int end=p.length();
        
        if(Arrays.equals(freq1,freq2))
            list.add(start);
        
        while(end<s.length()){
            
            freq1[s.charAt(start)-'a']--;
            freq1[s.charAt(end)-'a']++;
            
            if(Arrays.equals(freq1,freq2))
            list.add(start+1);
            
            start++;
            end++;
        }
    return list;  
    }        
}

3. Find All Anagrams in a String Solution JavaScript

var findAnagrams = function(s, p) { 
    let hash = {},  uniqueChars = 0;
    for (let c of p) {
        if (hash[c]==null) {
            uniqueChars++;
            hash[c] = 1;
        } else {
            hash[c]++;
        }
    }
    let res = [];
    let left = 0, right = 0;
    for (right;right<s.length;right++) {
        if (hash[s[right]]!=null) hash[s[right]]--;
        if (hash[s[right]]==0) uniqueChars--;
        if (uniqueChars==0) res.push(left);
        if (right - left + 1 == p.length) {
            if (hash[s[left]]!=null) hash[s[left]]++;
            if (hash[s[left++]]==1) uniqueChars++;
        }
    }
    return res;
};

4. Find All Anagrams in a String Solution Python

class Solution(object):
    def findAnagrams(self, s, p):
        myDictP=collections.Counter(p)
        myDictS=collections.Counter(s[:len(p)])
        output=[]
        i=0
        j=len(p)
        while j<=len(s):
            if myDictS==myDictP:
                output.append(i)
            myDictS[s[i]]-=1
            if myDictS[s[i]]<=0:
                myDictS.pop(s[i])
            if j<len(s):    
                 myDictS[s[j]]+=1
            j+=1
            i+=1
        return output