Question is simple,
given 3 letters, O represents on time, L represents Late, A represents absent.
A student can not have more than 3 absences in total(2 can be back to back), or 2 late next to each other(can not be back to back).

Given a size N, how many valid combinations can we have?

I used dfs with prunning, but a more optimal solution exists as hinted the the interviewer.
For example, a string starts with

1. LO....
2. OO....
   will have the same following combinations. So some way to save the already calculated number of combination is needed.
   I tried with end letter + current length as the hash, but the interviewer says AO is different, because ... for LO/OO can have A's in them, but AO contains a starting A, so some of the ... may contain invalid cases.

Can someone help with an answer?