← All solutions

The problem can be reformulated as follows: count the number of strings consisting of L/2 + 2 “R”:s and L/2 − 2 “O”:s such that there are no two adjacent “O”:s (where the first and the last positions are considered adjacent). This can be computed in O( L2 ) time and memory using dynamic programming.

There is also an O(1) solution to this problem.