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.