Problem

Given a word W and a string S, find all starting indices in S which are anagrams of W.

Examples

Example 1

1
2
3
4
5
6

Input: W = "ab", S = "abxaba"
Output: [0, 3, 4]
Explanation: 
- At index 0, the substring "ab" is an anagram of "ab".
- At index 3, the substring "ba" is an anagram of "ab".
- At index 4, the substring "ab" is an anagram of "ab".

Solution

Method 1 - Using Sliding Window

  • Use a sliding window approach to keep track of the frequency of characters in both the current window in S and the word W.
  • If the frequency counts match, it indicates an anagram.

Approach

  1. Calculate the length of W and S. If W is longer than S, return an empty list because it’s impossible to find any anagram.
  2. Create frequency maps for the characters in W and the first window of S with the length same as W.
  3. Slide the window one character at a time over S, updating the frequency map and checking for matches with the frequency map of W.
  4. Add the start index of the window to the result list when there’s a match.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public List<Integer> findAnagrams(String s, String w) {
        List<Integer> ans = new ArrayList<>();
        int sLen = s.length(), wLen = w.length();
        if (wLen > sLen) return ans;

        int[] wCount = new int[26];
        int[] sCount = new int[26];

        for (int i = 0; i < wLen; i++) {
            wCount[w.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i <= sLen - wLen; i++) {
            if (Arrays.equals(wCount, sCount)) ans.add(i);
            if (i + wLen < sLen) {
                sCount[s.charAt(i) - 'a']--;
                sCount[s.charAt(i + wLen) - 'a']++;
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findAnagrams(self, s: str, w: str) -> List[int]:
        s_len, w_len = len(s), len(w)
        if w_len > s_len:
            return []

        ans = []
        w_count = [0] * 26
        s_count = [0] * 26

        for i in range(w_len):
            w_count[ord(w[i]) - ord('a')] += 1
            s_count[ord(s[i]) - ord('a')] += 1

        for i in range(s_len - w_len + 1):
            if w_count == s_count:
                ans.append(i)
            if i + w_len < s_len:
                s_count[ord(s[i]) - ord('a')] -= 1
                s_count[ord(s[i + w_len]) - ord('a')] += 1

        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is length of string S, and m is length of string W.
    • Initial setup: O(m)
    • Sliding window: O(n-m)
    • Overall Time Complexity: O(n)
  • 🧺 Space complexity: O(26) = O(1), because we only need fixed space for the character set (usually 26 for lowercase English letters).