Find All Anagrams in a String

medium

Acceptance: 52%

StringsSliding Window

Two strings are given: a longer text and a shorter pattern. Locate every starting index within the text where a substring of the same length as the pattern is an anagram of the pattern. Return all such starting indices.

Examples

Example 1:

Input:text = "cbadcba", pattern = "abc"

Output:[0,4]

Explanation: At index 0, the substring 'cba' is an anagram of 'abc'. At index 4, the substring 'cba' is again an anagram.

Example 2:

Input:text = "xyzxyz", pattern = "zy"

Output:[1,4]

Explanation: Substrings 'yz' at positions 1 and 4 are both anagrams of 'zy'.

Hints

import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        int[] pCount = new int[26], sCount = new int[26];
        for (char c : p.toCharArray()) pCount[c - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
            if (i >= p.length()) sCount[s.charAt(i - p.length()) - 'a']--;
            if (Arrays.equals(pCount, sCount)) result.add(i - p.length() + 1);
        }
        return result;
    }
}

Time complexityO(n)

Space complexityO(1)

Find All Anagrams in a String

Examples

Hints

Related Problems