It's been a hectic day in production support land. My head hurts. And I still have stuff to do - will probably leave at around 21:30 PM, making this a 14 hours day.

Anyway, I skipped lunch and instead worked a bit on this problem. After much head scratching, came up with a O (N^2*M) dynamic programming solution (with N the length of the sequence and M the size of the alphabet). Was really proud of myself for about 3 minutes, until I noticed that N can be as large as 100000. Boom. Anyway, my worthless non- solution is here (sorry, in Java - as I said, I did it at work). Space can be reduced to just O(N*M), but that doesn't help with time.

laburu: I'll get around to answering your e-mail eventually, I swear.