Find All Anagrams in a String - Java Solution

1. Introduction

In this post, we will tackle the "Find All Anagrams in a String" problem. This problem involves finding all the start indices of anagrams of a given string p within another string s. An anagram is formed by rearranging the letters of a word or phrase, using all original letters exactly once.

Problem

Given two strings s and p, the task is to return an array of all the start indices of p's anagrams in s. The answer may be returned in any order.

Example:

- Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

- Input: s = "abab", p = "ab"

Output: [0, 1, 2]

2. Solution Steps

1. Use a sliding window approach to traverse the string s.

2. Maintain two arrays (or HashMaps) for character counts of p and the current window in s.

3. Slide the window across s, updating the character counts.

4. When the window size equals the length of p, compare the character counts of the window with those of p.

5. If the counts match, add the start index of the window to the result list.

6. Slide the window forward by removing the start character and adding the next character.

7. Repeat the process until the end of s is reached.

8. Return the list of start indices.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class FindAllAnagramsInString {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p)); // Test the function
    }

    // Function to find all anagrams in the string
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }

        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }

        int left = 0, right = 0;
        while (right < s.length()) {
            sCount[s.charAt(right) - 'a']++;

            if (right - left == p.length() - 1) {
                if (matches(sCount, pCount)) {
                    result.add(left);
                }
                sCount[s.charAt(left) - 'a']--;
                left++;
            }
            right++;
        }
        return result;
    }

    // Helper function to compare character counts
    private static boolean matches(int[] sCount, int[] pCount) {
        for (int i = 0; i < 26; i++) {
            if (sCount[i] != pCount[i]) {
                return false;
            }
        }
        return true;
    }
}

Output:

[0, 6]

Explanation:

1. findAnagrams: This function returns the starting indices of all anagrams of p in s.

2. The function initializes two count arrays (or HashMaps) for the characters of p and the current window in s.

3. It then uses a sliding window to traverse s, keeping track of the character counts in the current window.

4. When the window size equals the length of p, it compares the character counts. If they match, the start index of the window is added to the result list.

5. The window is slid forward by one character at a time, updating the counts accordingly.

6. The process continues until the end of s is reached, collecting all valid start indices.

7. matches: This helper function compares the character counts of p and the current window in s.

8. This method offers an efficient solution to the problem, with a time complexity of O(n) where n is the length of s.