Assume that the current string does not contain SCSC.

After deleting one character, a new SCSC can appear only when the two sides of the deleted character become adjacent and form SCSC.

In other words, before deletion, the string must contain SCSC with one extra character inserted into it. Since the string itself must not already contain SCSC, the only possible patterns are

SCCSC

and

SCSSC.

Therefore, if the current string contains either SCCSC or SCSSC, the current player can delete the middle extra character and win immediately.

Now call a state safe if it contains none of SCSC, SCCSC, and SCSSC.

In a safe state, the current player cannot win immediately. Also, if we delete the last character, no new adjacency is created. Hence the resulting string is still safe.

Therefore, in safe states, both players can avoid giving the opponent an immediate win, and the game becomes equivalent to simply decreasing the length by \(1\) each turn.

The empty string is losing for the current player. Hence, among safe states, even length is losing and odd length is winning.

Thus, Terra wins exactly in the following cases:

• the length of the string is odd;
• the length of the string is even, and the string contains SCCSC or SCSSC.

In all other cases, Lulu wins.

It is enough to scan the string and check whether either pattern appears.

The total time complexity is \({\cal O}(\sum |S|)\).