No Three in a Row — Solution & Editorial
State = (last symbol, current run length ∈ {1,2}); a third repeat is forbidden. Six states; raise the transfer matrix to the (N−1)-th power.
Complexity: O(log N)
State = (last symbol, current run length ∈ {1,2}); a third repeat is forbidden. Six states; raise the transfer matrix to the (N−1)-th power.
Complexity: O(log N)