Substring Anagram Detection — Problem Statement & Solution Guide
Sliding WindowMediumSliding Window / Hash Map
TimeO(n*m*log(m))
|SpaceO(m)
Problem Description
Given a string s and a target string t, determine if any anagram of t exists as a contiguous substring within s. Return true if found, and false otherwise.
Examples
Example 1
Input
s = 'abxaba', t = 'ab'
Output
true
Explanation: Step-by-step: with input s = 'abxaba' and t = 'ab', we create a sliding window of size 2 (length of t) and compare the sorted characters in the window with the sorted characters in t. We find a match at index 0 and 3, so we return true.
Example 2
Input
s = 'abc', t = 'bca'
Output
true
Explanation: Step-by-step: with input s = 'abc' and t = 'bca', we create a sliding window of size 3 (length of t) and compare the sorted characters in the window with the sorted characters in t. We find a match at index 0, so we return true.
Constraints
- 1 <= s1.length, s2.length <= 10^4
- s1 and s2 consist of lowercase English letters.
Optimal Approach & Strategy
Fixed sliding window of size s1.length. Maintain character frequencies of s1 and current window in s2. If frequencies match, return true. Time O(N), Space O(1).
Brute Force Approach
Generate all permutations of s1 and search. Time O(N!).
Verified Code Solutions
JavaScript Solution
Time: O(n*m*log(m))
function isAnagramSubstring(s, t) {
if (t.length > s.length) return false;
const tCount = {};
for (let char of t) {
if (!tCount[char]) tCount[char] = 0;
tCount[char]++;
}
const windowCount = {};
for (let i = 0; i < t.length; i++) {
if (!windowCount[s[i]]) windowCount[s[i]] = 0;
windowCount[s[i]]++;
}
if (isAnagram(windowCount, tCount)) return true;
for (let i = t.length; i < s.length; i++) {
windowCount[s[i - t.length]]--;
if (windowCount[s[i - t.length]] === 0) delete windowCount[s[i - t.length]];
if (!windowCount[s[i]]) windowCount[s[i]] = 0;
windowCount[s[i]]++;
if (isAnagram(windowCount, tCount)) return true;
}
return false;
};
function isAnagram(count1, count2) {
for (let key in count1) {
if (count1[key] !== count2[key]) return false;
}
for (let key in count2) {
if (count2[key] !== count1[key]) return false;
}
return true;
}class Solution {
public:
bool isAnagramSubstring(string s, string t) {
if (t.length() > s.length()) return false;
int tCount[26] = {0};
for (char c : t) {
tCount[c - 'a']++;
}
int windowCount[26] = {0};
for (int i = 0; i < t.length(); i++) {
windowCount[s[i] - 'a']++;
}
if (isAnagram(windowCount, tCount)) return true;
for (int i = t.length(); i < s.length(); i++) {
windowCount[s[i - t.length()] - 'a']--;
if (windowCount[s[i - t.length()] - 'a'] == 0) {
// do nothing
}
windowCount[s[i] - 'a']++;
if (isAnagram(windowCount, tCount)) return true;
}
return false;
}
bool isAnagram(int count1[26], int count2[26]) {
for (int i = 0; i < 26; i++) {
if (count1[i] != count2[i]) return false;
}
return true;
}
};class Solution {
public boolean isAnagramSubstring(String s, String t) {
if (t.length() > s.length()) return false;
int[] tCount = new int[26];
for (char c : t.toCharArray()) {
tCount[c - 'a']++;
}
int[] windowCount = new int[26];
for (int i = 0; i < t.length(); i++) {
windowCount[s.charAt(i) - 'a']++;
}
if (isAnagram(windowCount, tCount)) return true;
for (int i = t.length(); i < s.length(); i++) {
windowCount[s.charAt(i - t.length()) - 'a']--;
if (windowCount[s.charAt(i - t.length()) - 'a'] == 0) {
// do nothing
}
windowCount[s.charAt(i) - 'a']++;
if (isAnagram(windowCount, tCount)) return true;
}
return false;
}
public boolean isAnagram(int[] count1, int[] count2) {
for (int i = 0; i < 26; i++) {
if (count1[i] != count2[i]) return false;
}
return true;
}
}def is_anagram_substring(s, t):
if len(t) > len(s):
return False
t_count = {}
for char in t:
if char not in t_count:
t_count[char] = 0
t_count[char] += 1
window_count = {}
for i in range(len(t)):
if s[i] not in window_count:
window_count[s[i]] = 0
window_count[s[i]] += 1
if is_anagram(window_count, t_count):
return True
for i in range(len(t), len(s)):
window_count[s[i - len(t)]] -= 1
if window_count[s[i - len(t)]] == 0:
del window_count[s[i - len(t)]]
if s[i] not in window_count:
window_count[s[i]] = 0
window_count[s[i]] += 1
if is_anagram(window_count, t_count):
return True
return False
def is_anagram(count1, count2):
for key in count1:
if count1[key] != count2[key]:
return False
for key in count2:
if count2[key] != count1[key]:
return False
return Truefunction isAnagramSubstring(s, t) {
if (t.length > s.length) return false;
const tCount = {};
for (let char of t) {
if (!tCount[char]) tCount[char] = 0;
tCount[char]++;
}
const windowCount = {};
for (let i = 0; i < t.length; i++) {
if (!windowCount[s[i]]) windowCount[s[i]] = 0;
windowCount[s[i]]++;
}
if (isAnagram(windowCount, tCount)) return true;
for (let i = t.length; i < s.length; i++) {
windowCount[s[i - t.length]]--;
if (windowCount[s[i - t.length]] === 0) delete windowCount[s[i - t.length]];
if (!windowCount[s[i]]) windowCount[s[i]] = 0;
windowCount[s[i]]++;
if (isAnagram(windowCount, tCount)) return true;
}
return false;
};
function isAnagram(count1, count2) {
for (let key in count1) {
if (count1[key] !== count2[key]) return false;
}
for (let key in count2) {
if (count2[key] !== count1[key]) return false;
}
return true;
}Asked in Top Tech Interviews
Paytm
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.