Create an automaton with states corresponding to three-coin sequences, and a
transition function describing how state changes after including a next coin.
Initial state of automation would be the one that corresponds to first three
coins in input. As automaton progresses through coin sequence it counts how
many times it have been in each state, i.e., how many times each three-coin
sequence occurred.
It could be quite wordy to actually write down the transition function, but if
you treat three-coin sequences as numbers in binary, you end up with concise
(but implicit) description of transition function.