Find All Anagrams In A String - Leetcode Solution

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<int> findAnagrams(string s, string p) { vector<int> result; if(s.size()<p.size()) return result; unordered_map<char,int> 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)

1