algoadvance

Leetcode 438. Find All Anagrams in a String

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

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

Clarifying Questions

  1. Constraints on the input strings s and p?
    • 1 <= s.length, p.length <= 3 * 10^4
    • s and p consist of lowercase English letters.
  2. Can we assume that inputs are valid (i.e., s and p are always lowercase and non-empty)?
    • Yes, based on the problem constraints.
  3. Is maintaining the order of output significant?
    • No, the problem statement allows returning the output in any order.

Strategy

To solve this problem effectively, we can use a sliding window approach along with a frequency counter. Here’s the step-by-step strategy:

  1. Count Frequency of Characters in p:
    • Create a frequency array p_count for p.
  2. Initialize a Sliding Window:
    • Start with the first window in s that has the same length as p.
    • Populate the frequency array s_count for this window.
  3. Slide the Window and Compare:
    • Slide the window one character at a time across s.
    • For each new position, update the s_count by including the new character and excluding the old character from the frequency array.
    • Compare s_count with p_count. If they match, record the start index of the window.
  4. Edge Cases:
    • If p is longer than s, it’s impossible to find an anagram, so return an empty array.

Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    vector<int> p_count(26, 0), s_count(26, 0);
    
    int p_len = p.length(), s_len = s.length();
    if (p_len > s_len) return result;
    
    // Count frequency of characters in p
    for (char c : p) {
        p_count[c - 'a']++;
    }
    
    // Initialize the first window in s
    for (int i = 0; i < p_len; i++) {
        s_count[s[i] - 'a']++;
    }
    
    // Compare initial window
    if (s_count == p_count) {
        result.push_back(0);
    }
    
    // Slide the window over s
    for (int i = p_len; i < s_len; i++) {
        s_count[s[i] - 'a']++;                  // Add new character to window
        s_count[s[i - p_len] - 'a']--;          // Remove old character from window
        
        // Compare current window with p frequency
        if (s_count == p_count) {
            result.push_back(i - p_len + 1);
        }
    }
    
    return result;
}

int main() {
    string s = "cbaebabacd";
    string p = "abc";
    vector<int> indices = findAnagrams(s, p);
    
    for (int index : indices) {
        cout << index << " ";
    }
    
    return 0;
}

Time Complexity

The time complexity for this approach is O(n) where n is the length of s. This is because:

Hence, the overall complexity is O(n+m), which simplifies to O(n) since m ≤ n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI