String Problem

1

Hi,
Can anybody help me in this problem:CodeChef: Practical coding for everyone

@everule1 @carre @ssjgz

Thanks

2

Ok so let’s consider an array, where the ith element is 2^{r(S_i)}, where r(c) is 0 for a, 1 for b and so on.

Now we can notice, that each partition, must have xor sum of either 0, or 2^i. Now if you take prefix sums, you can nicely maintain this information. Let p_i be prefix xor sum of first i elements.

So now, dp transition is

dp_i = \min_{p_j = p_i \oplus x}{dp_j} + 1

where x is 2^i or 0.
You can implement this in O(nL_{eng} + 2^{L_{eng}}) or O(nL_{eng}\log{n}).

L_{eng} = 26 here.

5 Likes
3

Too good, 100 likes!!