Last updated on January 5th, 2025 at 11:58 pm
Here, we see a Find All Anagrams in a String LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table
Companies
Amazon
Level of Question
Medium
Find All Anagrams in a String LeetCode Solution
Table of Contents
1. 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”.
2. Coding Pattern Used in Solution
The provided code uses the Sliding Window pattern. This pattern is commonly used for problems involving contiguous subarrays or substrings, where the goal is to find a specific property (e.g., sum, frequency, or match) within a fixed-size or variable-size window. Here, the window size is fixed to the length of string p
, and the algorithm slides the window across string s
to find all starting indices of substrings in s
that are anagrams of p
.
3. Code Implementation in Different Languages
3.1 Find All Anagrams in a String 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; } };
3.2 Find All Anagrams in a String 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.3 Find All Anagrams in a String 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; };
3.4 Find All Anagrams in a String 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
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(1) |
Java | O(n) | O(1) |
JavaScript | O(n) | O(k) |
Python | O(n) | O(k) |
where,n
is the length of string s
.k
is the number of unique characters in p
.