- create a copy of p that is sorted for comparison
- sliding window of size p
- iterate through s, assign the values of our substring inside the window
- sort that string
- check if it is equal to p sorted
- if it is, push the inde for the left pointer of the window into the vector
🤔What Did I Struggle With?
- this works but is quite inefficient
- O((n-k) * k log k) space complexity
Inefficient Solution
💡 Explanation of Solution
1. frequency arrays
- pFreq to keep track of character frequencies in p
- windowFreq to keep track of the character frequencies in our current window
2. sliding window
- add the character at the right index to windowFreq
- if the window size exceeds p.size() remove the character at the left index from windowFreq and increment left
3. comparison
- if windowFreq equals pFreq, it means the current window is an anagram of p
⌛ Complexity Analysis
Time Complexity is O(n)
Space Complexity is O(n)
- frequency arrays fixed size of 26
- results vector with a worst case size of N
- therefore dominant factor for space if O(n)
💻 Implementation of Solution
class Solution {public: vector<int> findAnagrams(string s, string p) { vector<int> result; if (p.size() > s.size()) return result; // Frequency arrays for `p` and the current window in `s` vector<int> pFreq(26, 0), windowFreq(26, 0); // Fill the frequency array for `p` for (char c : p) { pFreq[c - 'a']++; } // Sliding window on `s` int left = 0, right = 0; while (right < s.size()) { // Add the current character to the window windowFreq[s[right] - 'a']++; // If the window size exceeds `p.size()`, remove the leftmost character if (right - left + 1 > p.size()) { windowFreq[s[left] - 'a']--; left++; } // Compare frequency arrays if (windowFreq == pFreq) { result.push_back(left); } // Move the right pointer right++; } return result; }};
💻Inefficient Implementation of Solution
class Solution {public: vector<int> findAnagrams(string s, string p) { vector<int> result; // Sort the pattern string to compare string copyP = p; sort(copyP.begin(), copyP.end()); // Define the sliding window bounds int left = 0; int right = p.size() - 1; // Iterate over the string `s` with a fixed window size while (right < s.size()) { // Extract the substring for the current window string subStrWindow = s.substr(left, p.size()); // Sort the substring window sort(subStrWindow.begin(), subStrWindow.end()); // Compare sorted substring with the sorted pattern if (subStrWindow == copyP) { result.push_back(left); } // Move the sliding window left++; right++; } return result; }};