Recursion, Catalan Numbers & Generating Functions · Medium problem

How many length-$6$ binary strings contain no three consecutive $1$s (no “$111$”)?