Given a word pat and a text txt. Return the count of the occurrences of anagrams of the word in the text

Question

Given a word pat and a text txt. Return the count of the occurrences of anagrams of the word in the text.

Example 1:

Input: txt = forxxorfxdofr pat = for Output: 3 Explanation: for, orf and ofr appears in the txt, hence answer is 3.

i tried using sliding window approach but didn't get the desired output! where am i wrong?

here's my code :

int search(string pat, string txt)
{

    string s = "";
    int n = txt.size();
    int k = pat.size();
    int i = 0;
    int j = 0;
    int count = 0;
    sort(pat.begin(), pat.end());
    while (j < n)
    {

        s += txt[j];


        if (j - i + 1 < k)
        {
            j++;
        }

        else if (j - i + 1 == k)
        {

            string temp = s;
            sort(temp.begin(), temp.end());
            if (temp == pat)
            {
                count++;
            }
            // size_t index = i;
            s.erase(i, 1);

            i++;
            j++;
        }
    }

    return count;
}

Answer 1

Stepping the code in a debugger shows that on the third iteration s is "oxx" not "rxx". It then becomes clear that you need to erase the first character from s not the i^th.

Change:

    s.erase(i, 1);

to

    s.erase(0, 1);

I have not tested with other input but for your example it return 3.

Note that you have somewhat over complicated the implementation (in my opinion). The following is exactly your algorithm, but simpler and easier to understand code (again in my opinion).

#include <string.h>
#include <algorithm>

using namespace std ;

int search(string pat, string txt)
{
    size_t patlen = pat.size();
    int end = txt.size() - patlen ;
    int count = 0;

    sort(pat.begin(), pat.end());

    for( int i = 0; i <= end; i++ )
    {
        string subtxt = txt.substr( i, patlen ) ;
        sort(subtxt.begin(), subtxt.end());
        if( subtxt == pat)
        {
            count++;
        }
    }

    return count;
}

As a matter of style, efficiency and const-correctness, I'd recommend changing the interface to search() as follows:

int search( const string& patr, const& string txt )
{
    string pat( patr ); // modifiable copy

    ...