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 get any lead .