Rt factor of a string

The rt factor of a string is defined as the number of times ‘abba’ is occurring in the given string as a substring. Given two integers length of string N and Rt factor find number of strings of length N containing ‘abba’ as their substring exactly Rt times.

Example

          abbabb -- rt factor is 1.
   
          abbabbabb -- rt factor is 2. Overlaps has to be considered.

Test case

Input

N = 10 and Rt = 2

output

74357

Note that string contains only lowercase english alphabet letters.(26 letters)

1<=N<=500
K can be anything.

Expected Time complexity --> O(N^2)

Can anyone please help me with the solution for this problem i am thinking it in terms of DP but didn’t got any lead .

1 Like

#include<bits/stdc++.h>
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;

int main()
{ quick;
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

string s;
cin>>s;
ll n=s.length();
ll i,cnt=0;
for(i=0;i<n-3;i++)
{
	if(s[i]=='a')
	{
		string s1=s.substr(i,4);
		if(s1=="abba")
		{
			cnt++;
		}
	}
}
cout<<cnt<<endl;

cerr << “time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs” << endl;
return 0;
}

Try this code…hopefully it will work fine.

You have integer not a string. It is told to find total different types of string

@anon56102475 Actually ashish is right you have been given an integer not the string and you need to count all the strings of length N that contains ‘abba’ rt times as their substring. See example test case for more clarity.