Let \(t\) be a string which is initially empty. We can solve the problem by repeating the following until \(s\) becomes empty.

• Remove the character at the beginning of \(s\) and append it to the end of \(t\). Then, if the last three characters in \(t\) are fox, remove those characters.

It works in \(O(N)\) time and is fast enough.