Doubt regarding a DP question

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.


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

Test case


N = 10 and Rt = 2



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

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 .

1 Like