×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Count Occurrences of Anagrams

In this article, we are going to see how to count no of anagrams using the sliding window concept? This problem has been featured in Amazon interview rounds.
Submitted by Radib Kar, on March 13, 2019 [Last updated : March 20, 2023]

Problem Description

Given a string S and a word C, return the count of the occurrences of anagrams of the word in the text. Both string and word are in lowercase letter.

Examples

    Input:
    S=fororfrdofr
    C=for

    Output:
    3
    
    Input:
    S=aabaabaa
    C=aaba
    
    Output:
    4

Example with explanation

Anagrams:

Two words are known to be anagrams of each other if they are of same length & use same set of characters with same frequencies.

"aba" and "baa" are anagrams since both have two a's and one b.

"aba" and "bab" are not anagrams.

For the First example:

    Input:
    S=fororfrdofr
    C=for

    S:
    0	1	2	3	4	5	6	7	8	9	10
    f	o	r	o	r	f	r	d	o	f	r

    S(0,2): for
    Thus S(0,2) is anagram of w

    S(3,5) : orf
    Thus S(3,5) is anagram of w

    S(8,10) : ofr
    Thus S(8,10) is anagram of w

    Thus count of occurrences of anagrams: 3

Pre-requisite:

  1. FUNCTION to check whether to word is anagram or not
    Check(string s1, string s2): returns true or false based or anagram detection
  2. String::substr(int i,int j): returns substring of length j from index i

Algorithm

    1.  Set count=0;
        For i=0:i<a.length()-b.length()+1
            IF (check(a.substr(i,b.length()),b))
            count++;
    2.  Print count

So the idea is pretty simple. What we are doing is to slide the window and check for anagrams. Window is nothing but the substring being extracted every time. Window length is equal to the word length.


To check anagrams

FUNCTION check(string a, string b)

1.  Declare a map  m; //to store frequency of each character
2.  For string abuild the map
    For (int i=0;i<a.length();i++)
        m[a[i]]++;
    END FOR
3.  For string bdestruct the map.
    For (int i=0;i<b.length();i++)
        m[b[i]]--;
    END FOR
4.  If map is totally destructed that means all key has value perfectly 0 
        return true;
    Else 
        Return false.

END FUNCTION

So this basically means, we are constructing a container using the elements of string a. Then we are destructing the map to form string b. If such formation is possible they strings are anagrams of each other.

C++ implementation of Count Occurrences of Anagrams

#include <bits/stdc++.h>
using namespace std;

bool check(string a, string b)
{
    //checking anagrams
    map<char, int> m;
    for (int i = 0; i < a.length(); i++)
        m[a[i]]++;
    for (int i = 0; i < b.length(); i++)
        m[b[i]]--;
    for (auto it = m.begin(); it != m.end(); it++)
        if (it->second != 0)
            return false;
    return true;
}

int countNoOfAnagram(string a, string b)
{
    int count = 0;
    //sliding window
    for (int i = 0; i < a.length() - b.length() + 1; i++) {
        if (check(a.substr(i, b.length()), b))
            count++;
    }
    return count;
}

int main()
{
    string S, C;

    cout << "Enter string S and word C\n";
    cin >> S >> C;

    cout << "No of anagrams: " << countNoOfAnagram(S, C) << endl;

    return 0;
}

Output

Enter string S and word C
fororfrdofr
for
No of anagrams: 3




Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.