Binary Substituition

Chef has a binary string $S$. He can replace any occurrence of - - $01$ with $a$ - $10$ with $b$ - $010$ with $ab$ - $101$ with $ba$ While doing these operations, Chef noticed that he can end up with different strings depending upon the order of application of the operations. Given the final string containing only $a$ and $b$, Chef wants to know the number of possible strings he might ha