Given a word pattern and a string text consisting of lowercase characters, find the count of substrings in text which are anagrams of the pattern.
Examples:
Input : text = "forxxorfxdofr", pattern = "for"
Output : 3
Explanation : Anagrams present are for, orf and ofr. Each appears in the text once and hence the count is 3.Input : text = "aabaabaa", pattern = "aaba"
Output : 4
Explanation : Anagrams present are aaba and abaa. Each appears twice in the text and hence the count is 4.
Try it on GfG Practice
Table of Content
[Naive] Substring Checking - O(n * m) time and O(1) space
Traverse the string and check every substring whose length equals the pattern. For each substring, verify whether it contains all the characters of the word.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to check if two strings are anagrams
bool areAnagram(string s1, string s2) {
vector<int> cnt(26, 0);
int n1 = s1.length();
int n2 = s2.length();
for (int i = 0; i < n1; i++)
cnt[s1[i] - 'a']++;
for (int i = 0; i < n2; i++)
cnt[s2[i] - 'a']--;
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0)
return false;
}
return true;
}
int search(string &pattern, string &text) {
// Initialize result
int res = 0;
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
// Check if substring and pattern are anagrams
if (areAnagram(text.substr(i, m), pattern))
res++;
}
return res;
}
int main() {
string text = "forxxorfxdofr";
string pattern = "for";
cout << search(pattern, text);
return 0;
}
class GfG {
// Function to check if two strings are anagrams
static boolean areAnagram(String s1, String s2) {
int[] cnt = new int[26];
int n1 = s1.length();
int n2 = s2.length();
for (int i = 0; i < n1; i++)
cnt[s1.charAt(i) - 'a']++;
for (int i = 0; i < n2; i++)
cnt[s2.charAt(i) - 'a']--;
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0)
return false;
}
return true;
}
static int search(String pattern, String text) {
// Initialize result
int res = 0;
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
// Check if substring and pattern are anagrams
if (areAnagram(text.substring(i, i + m), pattern))
res++;
}
return res;
}
public static void main(String[] args) {
String text = "forxxorfxdofr";
String pattern = "for";
System.out.println(search(pattern, text));
}
}
# Function to find if two strings are equal
def areAnagram(s1, s2):
cnt = [0] * 26
for i in range(len(s1)):
cnt[ord(s1[i]) - ord('a')] += 1
for i in range(len(s2)):
cnt[ord(s2[i]) - ord('a')] -= 1
for i in range(26):
if cnt[i] != 0:
return False
return True
def search(pattern, text):
# Initialize result
res = 0
for i in range(len(text) - len(pattern) + 1):
# Check if the pattern and substring are
# anagram of each other.
if areAnagram(text[i:i + len(pattern)], pattern):
res += 1
return res
if __name__ == "__main__":
text = "forxxorfxdofr"
pattern = "for"
print(search(pattern, text))
using System;
class GfG {
// Function to find if two strings are equal
static bool areAnagram(string s1, string s2) {
int[] cnt = new int[26];
for (int i = 0; i < s1.Length; i++)
cnt[s1[i] - 'a']++;
for (int i = 0; i < s2.Length; i++)
cnt[s2[i] - 'a']--;
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0) return false;
}
return true;
}
static int search(string pattern, string text) {
// Initialize result
int res = 0;
for (int i = 0; i < text.Length - pattern.Length + 1; i++) {
// Check if the pattern and substring are
// anagram of each other.
if (areAnagram(text.Substring(i, pattern.Length), pattern))
res++;
}
return res;
}
static void Main() {
string text = "forxxorfxdofr";
string pattern = "for";
Console.WriteLine(search(pattern, text));
}
}
// Function to find if two strings are equal
function areAnagram(s1, s2) {
let cnt = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++)
cnt[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
for (let i = 0; i < s2.length; i++)
cnt[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
for (let i = 0; i < 26; i++) {
if (cnt[i] !== 0) return false;
}
return true;
}
function search(pattern, text) {
// Initialize result
let res = 0;
for (let i = 0; i < text.length - pattern.length + 1; i++) {
// Check if the pattern and substring are
// anagram of each other.
if (areAnagram(text.substring(i, i + pattern.length), pattern))
res++;
}
return res;
}
// Driver code
let text = "forxxorfxdofr";
let pattern = "for";
console.log(search(pattern, text));
Output
3
[Optimal] Sliding Window - O(n + m) time and O(1) space
- Create a frequency array to track the difference between the pattern and the current window.
- Initialize the first window by updating counts for the pattern and the first substring.
- Slide the window one character at a time, updating counts for entering and leaving characters.
- If all counts become zero, the current window is an anagram.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Two strings are anagram if the count
// of characters of each string cancel
// each other out.
bool isAnagram(vector<int> &cnt) {
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0) return false;
}
return true;
}
int search(string &pattern, string &text) {
int m = pattern.length();
int n = text.length();
// If pattern length is greater than text length
if (m > n) return 0;
vector<int> cnt(26, 0);
// Count characters of pattern
for (char ch : pattern) {
cnt[ch - 'a']++;
}
// Process first window (size m-1)
for (int i = 0; i < m - 1; i++) {
cnt[text[i] - 'a']--;
}
int ans = 0;
// Sliding window
for (int i = m - 1; i < n; i++) {
// Add new character
cnt[text[i] - 'a']--;
// Check anagram
if (isAnagram(cnt)) ans++;
// Remove first character of window
cnt[text[i - m + 1] - 'a']++;
}
return ans;
}
int main() {
string text = "forxxorfxdofr";
string pattern = "for";
cout << search(pattern, text);
return 0;
}
class GfG {
// Two strings are anagram if the count
// of characters of each string cancel
// each other out.
static boolean isAnagram(int[] cnt) {
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0) return false;
}
return true;
}
static int search(String pattern, String text) {
int m = pattern.length();
int n = text.length();
// If pattern length is greater than text length
if (m > n) return 0;
int[] cnt = new int[26];
// Count characters of pattern
for (int i = 0; i < m; i++) {
char ch = pattern.charAt(i);
cnt[ch - 'a']++;
}
// Process first window (size m-1)
for (int i = 0; i < m - 1; i++) {
char ch = text.charAt(i);
cnt[ch - 'a']--;
}
int ans = 0;
// Sliding window
for (int i = m - 1; i < n; i++) {
// Add new character
char ch = text.charAt(i);
cnt[ch - 'a']--;
// Check anagram
if (isAnagram(cnt)) ans++;
// Remove first character of window
char toDel = text.charAt(i - m + 1);
cnt[toDel - 'a']++;
}
return ans;
}
public static void main(String[] args) {
String text = "forxxorfxdofr";
String pattern = "for";
System.out.println(search(pattern, text));
}
}
# Two strings are anagram if the count
# of characters of each string cancel
# each other out.
def isAnagram(cnt):
for i in range(26):
if cnt[i] != 0:
return False
return True
def search(pattern, text):
# If length of pattern is greater than
# text, then anagram is not possible.
if len(pattern) > len(text):
return 0
# Store the count of each char
# of pattern in an array.
cnt = [0] * 26
for ch in pattern:
cnt[ord(ch) - ord('a')] += 1
for i in range(len(pattern) - 1):
ch = text[i]
cnt[ord(ch) - ord('a')] -= 1
ans = 0
# Sliding window of size len(pattern)
for i in range(len(pattern) - 1, len(text)):
# Add the character in array
ch = text[i]
cnt[ord(ch) - ord('a')] -= 1
# If anagram exists
if isAnagram(cnt):
ans += 1
# Remove the first character of the
# window.
toDel = text[i - len(pattern) + 1]
cnt[ord(toDel) - ord('a')] += 1
return ans
if __name__ == "__main__":
text = "forxxorfxdofr"
pattern = "for"
print(search(pattern, text))
using System;
class GfG {
// Two strings are anagram if the count
// of characters of each string cancel
// each other out.
static bool isAnagram(int[] cnt) {
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0) return false;
}
return true;
}
static int search(string pattern, string text) {
// If length of pattern is greater than
// text, then anagram is not possible.
if (pattern.Length > text.Length) return 0;
// Store the count of each char
// of pattern in an array.
int[] cnt = new int[26];
foreach (char ch in pattern) {
cnt[ch - 'a']++;
}
for (int i = 0; i < pattern.Length - 1; i++) {
char ch = text[i];
cnt[ch - 'a']--;
}
int ans = 0;
// Sliding window of size pattern.Length
for (int i = pattern.Length - 1; i < text.Length; i++) {
// Add the character in array
char ch = text[i];
cnt[ch - 'a']--;
// If anagram exists
if (isAnagram(cnt)) ans++;
// Remove the first character of the
// window.
char toDel = text[i - pattern.Length + 1];
cnt[toDel - 'a']++;
}
return ans;
}
static void Main() {
string text = "forxxorfxdofr";
string pattern = "for";
Console.WriteLine(search(pattern, text));
}
}
// Two strings are anagram if the count
// of characters of each string cancel
// each other out.
function isAnagram(cnt) {
for (let i = 0; i < 26; i++) {
if (cnt[i] !== 0) return false;
}
return true;
}
function search(pattern, text) {
// If length of pattern is greater than
// text, then anagram is not possible.
if (pattern.length > text.length) return 0;
// Store the count of each char
// of pattern in an array.
let cnt = new Array(26).fill(0);
for (let ch of pattern) {
cnt[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let i = 0; i < pattern.length - 1; i++) {
let ch = text[i];
cnt[ch.charCodeAt(0) - 'a'.charCodeAt(0)]--;
}
let ans = 0;
// Sliding window of size pattern.length
for (let i = pattern.length - 1; i < text.length; i++) {
// Add the character in array
let ch = text[i];
cnt[ch.charCodeAt(0) - 'a'.charCodeAt(0)]--;
// If anagram exists
if (isAnagram(cnt)) ans++;
// Remove the first character of the
// window.
let toDel = text[i - pattern.length + 1];
cnt[toDel.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
return ans;
}
// Driver code
let text = "forxxorfxdofr";
let pattern = "for";
console.log(search(pattern, text));
Output
3