Definition
- Find all anagrams – returns the start index of every substring in
sof length|p|that is a permutation ofp. - Fixed-size window – the window width is exactly the pattern length; one character enters and one leaves per step.
- Combined count array – a single
int[26]initialized with pattern frequencies; entries are decremented on window entry and incremented on exit. - Matched counter – counts how many of the 26 entries are currently zero; when all 26 are zero, the window is an anagram.
- Complexity – O(|s| + |p|) time, O(alphabet size) space plus the output list.
At the National Bank of India, compliance defines a suspicious combination of transaction flags. The anti-money-laundering team scans each account's chronological flag stream for every position where a consecutive block matches the suspicious combination in any order, because each match is a window to investigate.
Understanding the Concepts
What is the Find All Anagrams problem?
Given a source string s and a pattern p, find the starting index of every substring of s that is an anagram (permutation) of p. For example, if s = "CBAEBABACD" and p = "ABC", the answer is [0, 6] because "CBA" at index 0 and "BAC" at index 6 are both anagrams of "ABC".
package com.bank.core;
// s = "CBAEBABACD", p = "ABC"
// Index 0: "CBA" -> anagram of "ABC" -> YES
// Index 1: "BAE" -> not anagram
// ...
// Index 6: "BAC" -> anagram of "ABC" -> YES
// Answer: [0, 6]
How is this different from Permutation in a String?
The algorithm is identical to the permutation-in-a-string problem. The only difference is the output: instead of returning true on the first match, you add the start index to a result list and continue sliding to the end.
package com.bank.core;
// Permutation in string: if (matches == 26) return true;
// Find all anagrams: if (matches == 26) result.add(right - pLen + 1);
// Same window, same counter, different output
How do you implement it?
Use the combined count array technique: initialize count[26] with the pattern's frequencies, decrement on character entry, increment on character exit, and track how many entries are zero.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class FindAllAnagrams {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length();
int pLen = p.length();
if (pLen > sLen) return result;
int[] count = new int[26];
for (char c : p.toCharArray()) count[c - 'A']++;
int matches = 0;
for (int i = 0; i < 26; i++) {
if (count[i] == 0) matches++;
}
for (int right = 0; right < sLen; right++) {
int in = s.charAt(right) - 'A';
count[in]--;
if (count[in] == 0) matches++;
else if (count[in] == -1) matches--;
if (right >= pLen) {
int out = s.charAt(right - pLen) - 'A';
count[out]++;
if (count[out] == 0) matches++;
else if (count[out] == 1) matches--;
}
if (matches == 26) {
result.add(right - pLen + 1);
}
}
return result;
}
public static void main(String[] args) {
FindAllAnagrams solver = new FindAllAnagrams();
System.out.println(solver.findAnagrams("CBAEBABACD", "ABC"));
System.out.println(solver.findAnagrams("ABAB", "AB"));
}
}
[0, 6]
[0, 1, 2]
How does the combined count array work step by step?
The count array starts with the pattern's frequencies. As characters enter the window, their count decrements toward zero. As characters leave, their count increments back. A zero entry means that character has exactly the right count in the window. When all 26 entries are zero, every character has the right count.
package com.bank.core;
// p = "AB", count = [A:1, B:1, others:0]
// Initial matches = 24 (24 chars already at 0)
// s = "BA..."
// Add 'B': count[B]=0, matches=25
// Add 'A': count[A]=0, matches=26 -> MATCH at index 0
// Remove 'B': count[B]=1, matches=25
// Add next char...
What are the edge cases?
Edge cases include: pattern longer than source (empty result), source is one long anagram (every position matches), single-character pattern and source, and overlapping anagrams.
package com.bank.core;
// Edge case 1: p longer than s -> empty list
// Edge case 2: s = "AAA", p = "A" -> [0, 1, 2] (every position)
// Edge case 3: s = "ABAB", p = "AB" -> [0, 1, 2] (overlapping matches)
// Edge case 4: s = p -> [0] (one match)
// Edge case 5: no matches -> empty list
What about a banking use case?
At the National Bank of India, the anti-money-laundering team defines a suspicious combination of transaction-type flags and scans each account's flag stream for every position where a consecutive block matches that combination in any order.
package com.bank.service;
import java.util.List;
public class SuspiciousPatternScanner {
private final FindAllAnagrams solver = new FindAllAnagrams();
public List<Integer> findSuspiciousWindows(
String flagStream, String suspiciousPattern) {
List<Integer> positions = solver.findAnagrams(flagStream, suspiciousPattern);
for (int pos : positions) {
System.out.println("ALERT: Suspicious block at position " + pos
+ ": " + flagStream.substring(pos, pos + suspiciousPattern.length()));
}
return positions;
}
public static void main(String[] args) {
SuspiciousPatternScanner scanner = new SuspiciousPatternScanner();
// C=cash, W=wire, F=foreign
scanner.findSuspiciousWindows("XCWFXFCWXWCF", "CWF");
}
}
ALERT: Suspicious block at position 1: CWF
ALERT: Suspicious block at position 5: FCW
ALERT: Suspicious block at position 9: WCF
What are common mistakes?
The most common mistake is collecting indices as substrings rather than integers, which wastes memory. Another mistake is stopping at the first match instead of continuing to the end. A third mistake is forgetting that the count array must include all 26 characters, not just those in the pattern, because characters not in the pattern must also have count zero in the window.
package com.bank.core;
// WRONG: collecting substrings -> wastes O(|p|) per match
result.add(s.substring(start, start + pLen)); // O(|p|) allocation each time
// CORRECT: collecting indices -> O(1) per match
result.add(right - pLen + 1);
What should a senior engineer know?
A senior engineer should know that this problem and permutation-in-a-string are the same algorithm with different output, and both belong to the fixed-size window template. The combined count array with a zero-tracking counter is the cleanest implementation, and the same technique applies to any problem asking for a fixed-size window with a frequency constraint.
For streaming pipelines, this can be implemented as an event-driven computation that fires an alert whenever the matched counter hits 26, processing each flag event in O(1) time.
package com.bank.core;
// Senior notes:
// 1. Same algorithm as permutation-in-string, different output
// 2. Combined count array: cleanest implementation
// 3. O(1) per slide with matched counter, even with many matches
// 4. Streaming: process each event in O(1), alert on match
// 5. Template covers: permutation check, all anagrams, any fixed-window frequency match
Visual Overview
Fixed-size window: s = "CBAEBABACD", p = "ABC" (width 3)
┌───────────┐
│ C B A │ E B A B A C D matches=26 -> record index 0
└───────────┘
┌───────────┐
C │ B A E │ B A B A C D not matching
└───────────┘
┌───────────┐
C B │ A E B │ A B A C D not matching
└───────────┘
┌───────────┐
C B A │ E B A │ B A C D not matching
└───────────┘
┌───────────┐
C B A E │ B A B │ A C D not matching
└───────────┘
┌───────────┐
C B A E B │ A B A │ C D not matching
└───────────┘
┌───────────┐
C B A E B A │ B A C │ D matches=26 -> record index 6
└───────────┘
┌───────────┐
C B A E B A B │ A C D │ not matching
└───────────┘
Result: [0, 6]
Key Takeaway
Find All Anagrams is the all-matches sibling of the permutation-in-a-string problem. The algorithm is identical: a fixed-size window of width equal to the pattern slides across the source, and a matched counter detects when the window's character counts align with the pattern's counts. The only difference is that instead of returning on the first match, you record every matching start index and continue to the end.
The combined count array technique makes the implementation clean: a single int[26] initialized with the pattern's frequencies serves as both the requirement and the window tracker. As characters enter the window, their count decrements; as they leave, it increments. When an entry reaches zero, that character has exactly the right count. Tracking how many entries are zero gives a constant-time match check per slide.
Because you collect indices rather than substrings, and each slide does constant work thanks to the matched counter, the algorithm stays O(|s| + |p|) even when there are many matches. The output list is the only per-match cost, and storing integer indices is minimal.
At the National Bank of India, the anti-money-laundering team scanned each account's chronological transaction-flag stream for every position where a consecutive block matched a suspicious combination in any order. Each match was a window for investigation. The constant work per slide and the linear-time guarantee kept the screening job fast even on high-volume accounts with frequent flag events.
Remember one sentence: use the same fixed-size window and matched counter as permutation-in-a-string, but collect every matching start index instead of returning on the first.
---