Find All Anagrams in String Java | Fresher Interview
Fast recall
Quick revision
Core answer
Can you combine fixed-size sliding window with frequency counting and do efficient array-based equality checks
Sorting each window substring to check for anagrams, giving O(n*k*log k) instead of using frequency arrays for O(1) comparison
Use Arrays.equals on two int[26] arrays for O(1) comparison and explain the frequency update when sliding
Interview-ready guide
Interview answer
To find all anagrams of a pattern in a string, I'd use a fixed-size sliding window with frequency counting.
First, I create two frequency arrays of size twenty six, one for the pattern and one for the current window. I build the pattern frequency array by iterating through the pattern and incrementing the count for each character. Then I initialize the window frequency array by processing the first k characters of the text, where k is the pattern length.
After that, I compare the two arrays using Arrays dot equals. If they match, the first window is an anagram, so I add index zero to my result list. Then I slide the window across the rest of the text.
At each position i starting from k, I update the window frequency by decrementing the count of the character leaving the window, which is at position i minus k, and incrementing the count of the character entering, which is at position i. After each update, I compare the two frequency arrays again. If they match, I add the start index of the current window to the result.
The start index is i minus k plus one, not i. The time complexity is O of n because I touch each character a constant number of times. The comparison using Arrays dot equals is O of twenty six, which is O of one for a fixed alphabet.
The key mistake to avoid is sorting each window substring to check for anagrams. That's O of n times k log k. Using frequency arrays with incremental updates is much faster and is the standard approach.
For example, in cbaebabacd with pattern abc, the first window cba has the same counts and starts at 0. After sliding one character at a time, bac matches again at index 6, so the answer is [0, 6].
Find All Anagrams in String Java | Fresher Interview
Direct Answer
Use a fixed-size sliding window equal to the pattern length, with character-frequency arrays for the window and the pattern. Slide one character at a time, updating frequencies; when the window's counts match the pattern's, an anagram starts at the current index. This runs in O(n) time using array comparison.
Deep Dive & Architecture
Every anagram of a pattern has the same length and the same character frequencies. Keep a window in the text whose size equals the pattern length, updating counts as one character enters and one leaves.
Worked example: text cbaebabacd, pattern abc
The first three-character window is cba, whose counts match abc, so record index 0. Slide to bae: remove c and add e, so it no longer matches. Continuing one position at a time eventually reaches bac at index 6, which matches again. The result is [0, 6].
For lowercase English letters, two arrays of 26 counts are easy to compare. A more optimized form tracks how many character counts currently match, avoiding a 26-cell comparison after every move. For a wider alphabet, use maps.
The window must be exactly the pattern length before recording a match. If the pattern is longer than the text, return an empty list. Define the behavior for an empty pattern instead of letting it produce an index at every position.
With a fixed alphabet, the algorithm is O(n) time and O(1) extra space. Map-based storage is O(k), where k is the number of distinct characters involved.
Code Example
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindAnagrams {
public static List<Integer> findAnagrams(String text, String pattern) {
List<Integer> result = new ArrayList<>();
if (text.length() < pattern.length()) return result;
int[] patternFreq = new int[26];
int[] windowFreq = new int[26];
for (char c : pattern.toCharArray()) patternFreq[c - 'a']++;
int k = pattern.length();
for (int i = 0; i < k; i++) windowFreq[text.charAt(i) - 'a']++; // first window
if (Arrays.equals(patternFreq, windowFreq)) result.add(0);
for (int i = k; i < text.length(); i++) {
windowFreq[text.charAt(i - k) - 'a']--; // remove leaving char
windowFreq[text.charAt(i) - 'a']++; // add entering char
if (Arrays.equals(patternFreq, windowFreq)) result.add(i - k + 1);
}
return result;
}
public static void main(String[] args) {
System.out.println(findAnagrams("cbaebabacd", "abc")); // [0, 6]
}
}
Common Mistakes & Pitfalls
- Sorting each window: extracting and sorting each substring is O(n * k log k). Use frequency arrays with O(1) comparison.
- Incorrect window start index: when a match is found at loop index i, the window starts at
i - k + 1, not i. - Using a HashMap when an array suffices: for lowercase letters,
int[26]is faster and simpler thanHashMap<Character, Integer>.
Check your understanding
Answer these without looking back at the article.
- What is the sliding window technique and when do you use it?
- How do you find the maximum sum subarray of size k?
- How do you find the longest substring without repeating characters?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.