Java: Find All Anagrams in a String

Thought Process

To find all anagrams of string 'p' in string 's', we use a sliding window approach with two frequency hashes. We first create a frequency hash for 'p'. Then, we slide a window of size p.size() over 's', maintaining a frequency hash for the current window. If the frequency hash of the window matches the frequency hash of 'p', we record the starting index of the window. This ensures we efficiently find all anagram's starting indices. 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> list = new ArrayList<>();

        if (p.length() > s.length())
            return list;

        int[] sHash = new int[26];
        int[] pHash = new int[26];

        for (int i = 0; i < p.length(); i++) {

            char ch = p.charAt(i);
            pHash[ch - 'a']++;
        }

        int start = 0;
        int end = 0;

        while (end < p.length()) {

            char ch = s.charAt(end);
            sHash[ch - 'a']++;
            end++;
        }
        if (Arrays.equals(sHash, pHash))
            list.add(0);

        while (end < s.length()) {

            char ch1 = s.charAt(start);
            char ch2 = s.charAt(end);

            sHash[ch1 - 'a']--;
            sHash[ch2 - 'a']++;

            end++;
            start++;

            if (Arrays.equals(sHash, pHash))
                list.add(start);
        }
        return list;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through s once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses fixed-size frequency hashes, ensuring constant space usage.

Code copied!