Substring Anagram Detection — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Sliding Window and solve the Substring Anagram Detection problem optimally.
O(n)O(1)Problem Description
Given two strings s and t consisting of lowercase English letters, determine whether s contains a contiguous substring that is a permutation of t. Return true if at least one such window exists, otherwise return false. The substring must have the same length as t and use exactly the same multiset of characters, possibly in a different order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Substring Anagram Detection"
WHY DOES IT MATTER?
Sliding‑window with constant‑size frequency tracking turns a quadratic‑time matching problem into linear time, which is essential for real‑time systems and large‑scale text processing where latency matters.
OPTIMIZATION CHALLENGE
The key insight is that moving the window by one position changes the multiset by exactly two characters—one exiting, one entering—so you can update the frequency diff in O(1) instead of recomputing from scratch.
REAL-WORLD CONNECTION
Think of a conveyor belt where each item represents a character; you only need to look at the items currently on the belt (the window) and adjust counts as items enter or leave, rather than recounting the whole belt each time.
During an interview, initialize the diff counter to zero, then increment for characters in t and decrement for the first window of s; a zero diff means a match, and you only need to adjust the diff when sliding, which makes the code both fast and easy to explain.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic sliding‑window variant of the anagram‑search problem. A naïve solution would generate every length‑|t| substring of s and compare its character frequency map to that of t, leading to O(|s|·|t|) time, which quickly becomes prohibitive for strings of length 10⁵ or more. The optimal approach leverages the fact that the alphabet is bounded (26 lowercase letters), allowing us to maintain a constant‑size frequency array for the current window and update it in O(1) as the window slides. By comparing the frequency arrays (or a diff counter) we can decide in constant time whether the current window is a permutation of t, yielding an overall linear scan. This paradigm—maintaining incremental state while moving a fixed‑size window—avoids recomputation and is the cornerstone of many substring‑search problems such as minimum‑window substring, longest substring with K distinct characters, and so on.
Interview Questions on This Problem
Q1How would you modify the sliding‑window solution if the strings could contain Unicode characters beyond the English alphabet?
Replace the fixed‑size 26‑element count array with a hash map (e.g., collections.Counter) to track character frequencies; the rest of the algorithm stays the same, but the space becomes O(k) where k is the number of distinct characters in t.
Q2At a fintech firm you need to detect fraudulent transaction patterns that are anagrams of a known malicious signature within a stream of transaction IDs. How does the sliding‑window technique help and what additional considerations are needed?
The sliding‑window lets you examine each contiguous block of IDs of length |signature| in O(1) amortized time, instantly flagging a match. In a streaming context you must handle unbounded input, so you keep only the current window state and discard older data, and you may need to incorporate thread‑safe structures or back‑pressure handling for high‑throughput streams.
Q3A startup asks you to extend the solution to return the starting indices of all anagram windows, not just a boolean. What changes are required?
Maintain the same sliding‑window logic, but each time the frequency arrays match, record the left pointer index in a result list. The algorithm’s time and space complexities remain O(n) and O(1) respectively (aside from the output list).
Examples
Input
s="abdcgh", t="cbd"
Output
true
Explanation: The substring "bdc" (indices 1‑3) contains the letters c,b,d exactly once, which is a permutation of t.
Input
s="aaaaa", t="aa"
Output
true
Explanation: Any two‑character window such as "aa" matches t because both consist of two a's.
Input
s="xyz", t="xyzz"
Output
false
Explanation: t is longer than s, so no substring of s can match its length; therefore the answer is false.
Constraints
- 1 <= s.length <= 10^5
- 1 <= t.length <= 10^5
- s and t contain only lowercase English letters
Optimal Approach & Strategy
Use a fixed‑size 26‑element array to store character differences and slide the window, updating two entries per move; this yields O(|s|) time and O(1) extra space.
Brute Force Approach
Generate every possible substring of length |t| and compare its sorted characters or frequency map to t’s; this costs O(|s|·|t|) time.
Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
function containsPermutation(s, t){
if(t.length > s.length) return false;
const need = new Array(26).fill(0);
for(const ch of t) need[ch.charCodeAt(0)-97]++;
const window = new Array(26).fill(0);
let required = need.filter(v=>v>0).length;
let formed = 0;
let left = 0;
for(let right=0; right<s.length; ++right){
const idx = s.charCodeAt(right)-97;
window[idx]++;
if(need[idx]>0 && window[idx]===need[idx]) formed++;
while(right-left+1 > t.length){
const lidx = s.charCodeAt(left)-97;
if(need[lidx]>0 && window[lidx]===need[lidx]) formed--;
window[lidx]--;
++left;
}
if(right-left+1===t.length && formed===required) return true;
}
return false;
}
if(input.length>=2){
const s = input[0];
const t = input[1];
console.log(containsPermutation(s,t) ? 'true' : 'false');
}#include <bits/stdc++.h>
using namespace std;
bool containsPermutation(const string &s, const string &t){
if(t.size() > s.size()) return false;
array<int,26> need{}; need.fill(0);
for(char c: t) need[c-'a']++;
array<int,26> window{}; window.fill(0);
int required = 0; for(int v: need) if(v>0) required++;
int formed = 0;
int left=0;
for(int right=0; right<(int)s.size(); ++right){
int idx = s[right]-'a';
window[idx]++;
if(need[idx]>0 && window[idx]==need[idx]) formed++;
while(right-left+1 > (int)t.size()){
int lidx = s[left]-'a';
if(need[lidx]>0 && window[lidx]==need[lidx]) formed--;
window[lidx]--;
++left;
}
if(right-left+1 == (int)t.size() && formed==required) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s,t; if(!(cin>>s>>t)) return 0;
cout<<(containsPermutation(s,t)?"true":"false");
return 0;
}import java.io.*;
public class Main {
public static boolean containsPermutation(String s, String t){
if(t.length() > s.length()) return false;
int[] need = new int[26];
for(char c: t.toCharArray()) need[c-'a']++;
int[] window = new int[26];
int required = 0;
for(int v: need) if(v>0) required++;
int formed = 0;
int left = 0;
for(int right=0; right<s.length(); ++right){
int idx = s.charAt(right)-'a';
window[idx]++;
if(need[idx]>0 && window[idx]==need[idx]) formed++;
while(right-left+1 > t.length()){
int lidx = s.charAt(left)-'a';
if(need[lidx]>0 && window[lidx]==need[lidx]) formed--;
window[lidx]--;
left++;
}
if(right-left+1 == t.length() && formed == required) return true;
}
return false;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line == null) return;
String[] parts = line.trim().split("\\s+");
if(parts.length < 2){
String line2 = br.readLine();
if(line2 != null) parts = new String[]{parts[0], line2.trim()};
}
String s = parts[0];
String t = parts[1];
System.out.print(containsPermutation(s, t) ? "true" : "false");
}
}import sys
def contains_permutation(s: str, t: str) -> bool:
if len(t) > len(s):
return False
need = [0]*26
for ch in t:
need[ord(ch)-97] += 1
window = [0]*26
required = sum(1 for v in need if v>0)
formed = 0
left = 0
for right,ch in enumerate(s):
idx = ord(ch)-97
window[idx] += 1
if need[idx]>0 and window[idx]==need[idx]:
formed += 1
while right-left+1 > len(t):
lidx = ord(s[left])-97
if need[lidx]>0 and window[lidx]==need[lidx]:
formed -= 1
window[lidx] -= 1
left += 1
if right-left+1 == len(t) and formed == required:
return True
return False
if __name__ == "__main__":
data = sys.stdin.read().split()
if len(data) >= 2:
s, t = data[0], data[1]
print(str(contains_permutation(s, t)).lower())
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
function containsPermutation(s, t){
if(t.length > s.length) return false;
const need = new Array(26).fill(0);
for(const ch of t) need[ch.charCodeAt(0)-97]++;
const window = new Array(26).fill(0);
let required = need.filter(v=>v>0).length;
let formed = 0;
let left = 0;
for(let right=0; right<s.length; ++right){
const idx = s.charCodeAt(right)-97;
window[idx]++;
if(need[idx]>0 && window[idx]===need[idx]) formed++;
while(right-left+1 > t.length){
const lidx = s.charCodeAt(left)-97;
if(need[lidx]>0 && window[lidx]===need[lidx]) formed--;
window[lidx]--;
++left;
}
if(right-left+1===t.length && formed===required) return true;
}
return false;
}
if(input.length>=2){
const s = input[0];
const t = input[1];
console.log(containsPermutation(s,t) ? 'true' : 'false');
}
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.