Definition
- Permutation in a string – determines whether any contiguous substring of
sof length|p|is an anagram ofp. - Fixed-size window – the window width is exactly the pattern length; one character enters on the right and one leaves on the left per step.
- Count signature – both the pattern and the window are represented as character-frequency arrays or maps.
- Matched counter – tracks how many distinct characters currently have exactly their required count, making each slide O(1).
- Complexity – O(|s| + |p|) time, O(alphabet size) space.
At the National Bank of India, a loan file requires a specific set of approval stamps in specific quantities but in any order. Rajesh scans a ledger of stamps and checks whether any consecutive block of exactly that size matches the required set in some order.
Understanding the Concepts
What is the Permutation in a String problem?
Given a source string s and a pattern p, determine whether s contains any permutation (anagram) of p as a contiguous substring. For example, if s = "EIDBAOOO" and p = "AB", the answer is true because the substring "BA" at index 3 is a permutation of "AB".
package com.bank.core;
// s = "EIDBAOOO", p = "AB"
// Substring "BA" at index 3-4 is a permutation of "AB"
// Answer: true
Why use a fixed-size window?
A permutation of the pattern has exactly the same length as the pattern. So we only need to check substrings of length |p|. A fixed-size window of width |p| slides across s, and at each position we check whether the window's character counts match the pattern's counts.
package com.bank.core;
// Pattern "ABC" has length 3
// Only substrings of length 3 can be permutations
// Fixed window of width 3 slides across the source
// One char enters, one char leaves per step -> constant work per slide
How does the matched counter work?
Comparing two full count arrays on every slide costs O(alphabet size) per step. The matched counter avoids this by tracking how many distinct required characters currently have exactly the right count. When a character enters the window and its count reaches the required amount, matched increments. When its count moves away from the required amount (goes one over), matched decrements. The mirror applies when a character leaves.
package com.bank.service;
public class PermutationInString {
public boolean checkInclusion(String p, String s) {
int pLen = p.length();
int sLen = s.length();
if (pLen > sLen) return false;
int[] need = new int[26];
int[] window = new int[26];
for (char c : p.toCharArray()) need[c - 'A']++;
int required = 0;
for (int n : need) if (n > 0) required++;
int matched = 0;
for (int right = 0; right < sLen; right++) {
// Add entering character
int in = s.charAt(right) - 'A';
window[in]++;
if (need[in] > 0 && window[in] == need[in]) matched++;
else if (need[in] > 0 && window[in] == need[in] + 1) matched--;
// Remove leaving character when window exceeds pattern size
if (right >= pLen) {
int out = s.charAt(right - pLen) - 'A';
if (need[out] > 0 && window[out] == need[out]) matched--;
else if (need[out] > 0 && window[out] == need[out] + 1) matched++;
// Wait: the logic is: before decrement, check crossing
// Actually let me rewrite correctly
}
// Remove leaving character (corrected logic)
if (right >= pLen) {
int out = s.charAt(right - pLen) - 'A';
if (need[out] > 0 && window[out] == need[out]) {
matched--; // about to drop below required
}
window[out]--;
if (need[out] > 0 && window[out] == need[out]) {
matched++; // dropped back to exactly required
}
}
if (matched == required) return true;
}
return false;
}
}
Let me provide a cleaner implementation:
package com.bank.service;
public class PermutationInString {
public boolean checkInclusion(String p, String s) {
int pLen = p.length();
int sLen = s.length();
if (pLen > sLen) return false;
int[] count = new int[26]; // combined count: need - window
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) return true;
}
return false;
}
public static void main(String[] args) {
PermutationInString solver = new PermutationInString();
System.out.println(solver.checkInclusion("AB", "EIDBAOOO"));
System.out.println(solver.checkInclusion("AB", "EIDCAOOO"));
}
}
true
false
How does the combined count array work?
Instead of two separate arrays, you can use a single count array initialized to the pattern's frequencies. As characters enter the window, you decrement; as they leave, you increment. When an entry reaches zero, that character has exactly the right count in the window. When all 26 entries are zero, the window is a permutation. Track the number of zero entries with a matches counter for O(1) checks per slide.
package com.bank.core;
// count[i] = need[i] - window[i]
// count[i] == 0 means character i has exactly the right amount
// matches == 26 means ALL characters have the right amount
// Characters not in the pattern start at 0 and stay 0 unless they appear in s
What are the edge cases?
Edge cases include: pattern longer than source (return false immediately), pattern and source are identical (return true), single-character pattern and source, and pattern with duplicate characters.
package com.bank.core;
// Edge case 1: p longer than s -> false
// Edge case 2: p == s -> true
// Edge case 3: p = "A", s = "A" -> true
// Edge case 4: p = "AAB", must find substring with 2 A's and 1 B
// Edge case 5: p = "A", s = "B" -> false
How is this different from Find All Anagrams?
This problem returns true/false on the first match. Find All Anagrams collects every matching start index. The algorithm is identical except that instead of returning on the first match, you add the start index to a list and continue.
| Aspect | Permutation in string | Find all anagrams |
|---|---|---|
| Output | boolean | List of start indices |
| First match | Return true | Add to list, continue |
| Template | Fixed-size window + matched counter | Same |
package com.bank.core;
// Permutation in string: if (matches == 26) return true;
// Find all anagrams: if (matches == 26) result.add(right - pLen + 1);
// Same algorithm, different output collection
What about a banking use case?
At the National Bank of India, loan files require a specific set of approval stamps in specific quantities but in any order. Rajesh checks whether any consecutive block in the stamp ledger matches the required set.
package com.bank.service;
public class ApprovalStampChecker {
private final PermutationInString solver = new PermutationInString();
public boolean hasValidApprovalBlock(String stampLedger, String requiredStamps) {
return solver.checkInclusion(requiredStamps, stampLedger);
}
public static void main(String[] args) {
ApprovalStampChecker checker = new ApprovalStampChecker();
// M=manager, A=auditor, S=senior
System.out.println(checker.hasValidApprovalBlock("XMMSAXASY", "MAS"));
System.out.println(checker.hasValidApprovalBlock("XMMXAXY", "MAS"));
}
}
true
false
What are common mistakes?
The most common mistake is comparing full count arrays on every slide instead of using the matched counter, which turns O(n) into O(n * alphabet). Another mistake is not handling the entering and leaving character updates symmetrically, leading to off-by-one in the matched count.
package com.bank.core;
// WRONG: comparing full arrays per slide -> O(n * 26)
for (int i = 0; i < sLen - pLen + 1; i++) {
if (Arrays.equals(window, need)) return true; // O(26) per step
}
// CORRECT: matched counter -> O(1) per slide
if (matches == 26) return true;
What should a senior engineer know?
A senior engineer should know that the matched counter is what separates a clean O(n) solution from a naive O(n * alphabet) one. The combined count array technique (need minus window in a single array) is slightly cleaner than maintaining two arrays because it uses one array and a single zero-check. This same fixed-window template solves the entire family of anagram-search problems.
package com.bank.core;
// Senior notes:
// 1. Matched counter: O(1) per slide vs O(26) array comparison
// 2. Combined count array: count[i] = need[i] - window[i], check for all zeros
// 3. Same template: permutation check, find-all-anagrams, any fixed-window frequency match
// 4. For lowercase only: int[26]; for full ASCII: int[128]
Visual Overview
Fixed-size window: s = "EIDBAOOO", p = "AB"
need: {A:1, B:1}, window width = 2
Slide the window:
┌───────┐
│ E I │ D B A O O O count not matching
└───────┘
┌───────┐
E │ I D │ B A O O O count not matching
└───────┘
┌───────┐
E I │ D B │ A O O O D:1, B:1 -> not matching AB
└───────┘
┌───────┐
E I D │ B A │ O O O B:1, A:1 -> MATCH!
└───────┘
return true
Combined count array visualization:
Initial: count = [A:1, B:1, others:0]
matches = 24 (24 chars already at 0)
Add 'E': count[E]=-1, matches=23
Add 'I': count[I]=-1, matches=22
Remove 'E': count[E]=0, matches=23
Add 'D': count[D]=-1, matches=22
Remove 'I': count[I]=0, matches=23
Add 'B': count[B]=0, matches=24
Remove 'D': count[D]=0, matches=25
Add 'A': count[A]=0, matches=26 -> MATCH!
Key Takeaway
Permutation in a String asks whether any contiguous substring of the source of length equal to the pattern is an anagram of the pattern. You solve it with a fixed-size sliding window of width equal to the pattern length. A count signature represents the pattern's character frequencies, and the window maintains a matching count. Each slide adds one character on the right and removes one on the left, with constant work per step.
The matched counter is what makes the solution efficient. Instead of comparing full count arrays on every slide, you track how many characters currently have exactly the right count. Each entering and leaving character updates this counter with symmetric logic: approaching the required count increments it, moving away decrements it. When all characters match, the window is a permutation. This turns an O(n * alphabet) solution into a clean O(n) one.
The combined count array technique is a compact alternative: initialize a single array with the pattern's frequencies, decrement on entry, increment on exit, and count how many entries are zero. When all entries are zero, every character has exactly the right count. This same template directly extends to the find-all-anagrams problem by collecting every matching position instead of returning on the first.
At the National Bank of India, Rajesh used this to check whether any consecutive block of approval stamps in a loan file's ledger matched the required stamp set in any order. The fixed window with a matched counter gave constant work per slide and a single linear pass per ledger, keeping the audit system responsive even for files with thousands of stamps.
Remember one sentence: slide a fixed-width window the size of the pattern and use a matched counter to detect when the character counts align in O(1) per step.
---