Find All Anagrams in a String

 

  1. Clarify the problem:

    • The problem requires us to find all the anagrams of a given string in another string.
    • An anagram is a word or phrase formed by rearranging the letters of another word or phrase.
    • We need to return the starting indices of all the anagrams found.
    • The input strings consist of lowercase English letters only.
    • The length of the input strings can range from 1 to 10^4.

  2. Analyze the problem:

    • Input: Two strings, s (the longer string) and p (the shorter string).
    • Output: A list of integers representing the starting indices of all the anagrams of p in s.
    • Constraints:
      • The input strings consist of lowercase English letters only.
      • The length of the input strings can range from 1 to 10^4.

  3. Design an algorithm:

    • We can use a sliding window approach to solve this problem.
    • First, we create a frequency map of the characters in the shorter string p.
    • Then, we iterate through the longer string s using a sliding window of length equal to the length of p.
    • For each window, we check if the frequency map of the window matches the frequency map of p.
    • If they match, we add the starting index of the window to the result list.

  4. Explain your approach:

    • We will create a frequency map of the characters in the shorter string p.
    • We will initialize two pointers, left and right, to represent the sliding window in the longer string s.
    • We will move the window from left to right and check if the frequency map of the window matches the frequency map of p.
    • If they match, we add the starting index of the window to the result list.
    • We will continue this process until the right pointer reaches the end of the longer string s.
    • Finally, we will return the result list.

  5. Write clean and readable code:

python
def findAnagrams(s, p):
    result = []
    len_s, len_p = len(s), len(p)
    if len_s < len_p:
        return result

    p_freq = [0] * 26
    s_freq = [0] * 26

    # Calculate frequency of characters in p
    for char in p:
        p_freq[ord(char) - ord('a')] += 1

    # Initialize sliding window
    for i in range(len_p):
        s_freq[ord(s[i]) - ord('a')] += 1

    # Check if first window is an anagram
    if s_freq == p_freq:
        result.append(0)

    # Slide the window and check for anagrams
    for i in range(len_p, len_s):
        s_freq[ord(s[i]) - ord('a')] += 1
        s_freq[ord(s[i - len_p]) - ord('a')] -= 1
        if s_freq == p_freq:
            result.append(i - len_p + 1)

    return result
  1. Test your code:
    • Let's test the code with the following test cases:
      • Test case 1: s = "cbaebabacd", p = "abc"
        • In this test case, the anagrams of p ("abc") in s ("cbaebabacd") are "cba" and "bac".
        • The starting indices of the anagrams are [0, 6].
      • Test case 2: s = "abab", p = "ab"
        • In this test case, the anagrams of p ("ab") in s ("abab") are "ab" and "ba".
        • The starting indices of the anagrams are [0, 1, 2].
python
print(findAnagrams("cbaebabacd", "abc"))  # Output: [0, 6]
print(findAnagrams("abab", "ab"))         # Output: [0, 1, 2]

  1. Optimize if necessary:

    • The sliding window approach used in the algorithm has a time complexity of O(len(s)) since we iterate through the longer string s only once.
    • The space complexity is O(1) since the frequency maps have a fixed size of 26.

  2. Handle error cases:

    • The given code assumes the input is valid and doesn't explicitly handle error cases like empty strings or strings with characters other than lowercase English letters. Additional error handling logic can be added to validate the input.

  3. Discuss complexity analysis:

    • Time complexity: O(len(s)), where len(s) is the length of the longer string s.
    • Space complexity: O(1), since the frequency maps have a fixed size of 26.
Next Post Previous Post