Can M*N*2^(n) dp solution be improved, so that it passes all test? ( Probably it could be M*2^(n)), or it's wrong and I have to think on completely new solution?

Yes. It can be easily optimized to O(N*log|S|*2^N).(|S| - is the length of the word). But even O(N*|S|*2^N) solution can pass all tests.

Well, my n * s * 2^n solution didn't pass until I added a (as it turned out) curcial optimization.

Edited by author 27.07.2009 03:08

My solution is s*2^n ... it runs extremely fast with a very short code :)

Edited by author 01.08.2010 16:59

Edited by author 01.08.2010 16:59

N*2^N exists.