Definition
This problem returns the start indexes of every substring of a text that is an anagram of a given pattern. A fixed-size sliding window the length of the pattern slides across the text, maintaining a character-frequency count that is compared against the pattern's frequency; a match means the window is an anagram. Using a matched-count optimization it runs in O(n) time and O(alphabet) space.
The National Bank of India looks for every place in a transaction-reference string where a window of characters is a rearrangement of a known suspicious code. Rajesh slides a fixed-width window the size of the code and keeps a tally of letters inside it; whenever the tally matches the code's tally, that starting spot is an anagram hit.
Understanding the Concepts
What is the problem?
Find All Anagrams in a String — Fixed-Size Window With Frequency Comparison. Find All Anagrams in a String — fixed-size window with frequency comparison.
How does the approach work?
Build a frequency array need of size 26 for the pattern. Slide a window of width equal to the pattern length over the text, keeping a window frequency array. For each new right index add its character to window, and once the window exceeds the pattern length, remove the leftmost character. Whenever the window width equals the pattern length, compare the two arrays; if equal, record the start index.
A faster variant uses a single matches counter instead of comparing 26 cells each step. It counts how many of the 26 letters currently have equal frequency in the window and the pattern, updating matches incrementally as characters enter and leave, and reports a hit when matches == 26. A code snippet of the simpler array-compare version: for (int r=0; r.
The two methods trade clarity for speed. Comparing arrays each step is O(26) per position, which is O(26n) overall, still linear in n with a constant factor. The matched-count version removes that constant factor and is the senior-level answer, but both are acceptable and the array-compare version is easier to get right under pressure.
A senior nuance is the off-by-one on when to start comparing: you only compare once the window has reached the full pattern width, which is at right index pattern-length minus one and every index after. Also remember to shrink the window by removing the character that falls off the left as the window advances, otherwise the window grows unbounded and the counts drift.
What is the banking use case?
The code shows an AnagramScanner with findAnagramStarts, a demo on a reference string and a pattern, and the list of start indexes.
How do you implement this in Java?
// ─── File: src/main/java/com/bank/fraud/FindAnagramsDemo.java ───
package com.bank.fraud;
import java.util.*;
import java.util.logging.*;
public class FindAnagramsDemo {
private static final Logger log = Logger.getLogger(FindAnagramsDemo.class.getName());
static {
Logger root = Logger.getLogger("");
for (Handler h : root.getHandlers()) root.removeHandler(h);
ConsoleHandler ch = new ConsoleHandler();
ch.setFormatter(new BankLogFormatter());
root.addHandler(ch);
root.setLevel(Level.ALL);
}
public static void main(String[] args) {
AnagramScanner scanner = new AnagramScanner();
String text = "cbaebabacd";
String pattern = "abc";
List<Integer> hits = scanner.findAnagramStarts(text, pattern);
log.info(() -> "Anagram start indexes of '" + pattern + "' in '" + text + "': " + hits);
}
}
// ─── Would be in AnagramScanner.java in a real project ───
class AnagramScanner {
private static final Logger log = Logger.getLogger(AnagramScanner.class.getName());
// Fixed-size window, frequency compare. O(26n) time, O(26) space.
List<Integer> findAnagramStarts(String text, String pattern) {
List<Integer> result = new ArrayList<>();
int pLen = pattern.length();
if (text.length() < pLen) return result;
int[] need = new int[26];
int[] window = new int[26];
for (int i = 0; i < pLen; i++) need[pattern.charAt(i) - 'a']++;
for (int r = 0; r < text.length(); r++) {
window[text.charAt(r) - 'a']++; // add entering char
if (r >= pLen) window[text.charAt(r - pLen) - 'a']--; // drop leaving char
if (r >= pLen - 1 && Arrays.equals(window, need)) {
result.add(r - pLen + 1); // window start index
}
}
log.info(() -> "Found " + result.size() + " anagram windows");
return result;
}
}
// ─── Would be in BankLogFormatter.java in a real project ───
class BankLogFormatter extends java.util.logging.Formatter {
@Override public String format(LogRecord r) {
return String.format("%1$tF %1$tT %2$-7s %3$s%n",
new java.util.Date(r.getMillis()), r.getLevel(), r.getMessage());
}
}
What is the project structure?
anagram-scanner-service/
├── pom.xml
└── src/
└── main/
└── java/com/bank/fraud/
└── FindAnagramsDemo.java (runnable demo)
How do you build and run?
# Compile
javac -d target/classes src/main/java/com/bank/fraud/FindAnagramsDemo.java
# Run
java -cp target/classes com.bank.fraud.FindAnagramsDemo
What is the step-by-step walkthrough?
Input: text "cbaebabacd", pattern "abc" of length 3. The need array has a 1, b 1, c 1.
2026-10-26 21:00:03 INFO Found 2 anagram windows
2026-10-26 21:00:03 INFO Anagram start indexes of 'abc' in 'cbaebabacd': [0, 6]
What is the high-level design?
═══ HLD — Anagram Fraud Scan ═══
┌───────────┐ trigger ┌──────────────────┐ read ┌────────────────┐
│ Fraud │────────→│ Anagram Scan Job │─────→│ Ref Strings DB │
│ Scheduler │ │ (Spring Batch) │ │ (read replica) │
└───────────┘ └────────┬─────────┘ └────────────────┘
│ O(n) slide
▼
┌──────────────────┐
│ Match Alerts │ → Kafka → SIEM
└──────────────────┘
What is the low-level design?
═══ LLD — Find All Anagrams ═══
┌─ Design Patterns Used ──────────────────────────────────┐
│ Service layer: AnagramScanner isolates logic │
│ Fixed-size window + frequency-array comparison │
└──────────────────────────────────────────────────────────┘
┌─ SOLID Principles Applied ──────────────────────────────┐
│ S: scanner scans; formatter formats │
│ O: matched-count optimization swappable, same contract │
└──────────────────────────────────────────────────────────┘
── Class Diagram ─────────────────────────────────────────
┌────────────────────────────────────────────┐
│ AnagramScanner │
│ ────────────────────────────────────────── │
│ + findAnagramStarts(text, pattern): │ List<Integer>
│ List<Integer> │ O(26n)
└────────────────────────────────────────────┘
Contract for findAnagramStarts:
Pre: lowercase letters, non-null
Post: all start indexes where window is anagram of pattern
Edge: text shorter than pattern → empty list
── State Diagram ─────────────────────────────────────────
[SLIDE] add right char; if width>pLen drop left char
│ ─width==pLen && freq match→ record start → [SLIDE]
▼
[right==n] → [DONE]
── Call Chain ────────────────────────────────────────────
1. main() → scanner.findAnagramStarts("cbaebabacd","abc")
2. → build need, slide window, compare
3. → return [0,6]
What is the time and space complexity?
Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.
What are common mistakes?
Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.
What are the edge cases?
Edge cases include empty input, single element input, all identical elements, and boundary values.
What should a senior engineer know?
A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.
Visual Overview
text="cbaebabacd" pattern="abc"
│
▼
slide width-3 window; compare window freq to need freq
│ window[0..2]="cba" == need → start 0
│ window[1..3]="bae" ≠
│ ...
│ window[6..8]="bac" == need → start 6
▼
Result: [0, 6]
Key Takeaway
Find All Anagrams in a String returns the starting index of every window in a text that is a rearrangement of a given pattern, and I solve it with a fixed-size sliding window the length of the pattern. I build a character-frequency count for the pattern, then slide a same-width window across the text, adding the character entering on the right and removing the character leaving on the left. Whenever the window reaches the pattern's width, I compare the window's frequency count against the pattern's; if they are equal the window is an anagram and I record its starting index.
There are two ways to do the comparison. The straightforward way compares the two frequency arrays at each position, which costs a constant factor of twenty-six per step and is still linear in the length of the text. The faster way maintains a single matched-letter counter that updates incrementally as characters enter and leave, reporting a hit when all twenty-six letters match, which removes that constant factor. Both are acceptable, and I usually reach for the array comparison first because it is easier to get right under pressure and mention the matched-count optimization as the improvement.
The details that catch people out are the off-by-one on when to start comparing, which is only once the window has grown to the full pattern width, and remembering to drop the character that slides off the left edge as the window advances, otherwise the counts drift and every later comparison is wrong.
In my banking project at the National Bank of India I used this in the fraud service. The team had a known suspicious character pattern and needed every position in a long transaction-reference string where a same-length window was a permutation of it, since fraud rings sometimes reorder a code. The reference strings were long, so the linear sliding comparison was essential rather than checking each substring independently. Explaining the window slide, the frequency comparison, the matched-count optimization, and the off-by-one and shrink details shows the interviewer I understand both the algorithm and the pitfalls.
Remember one sentence: understand the core algorithm and apply it to banking domain problems.
---