Hello there,

Several days ago I came across this problem 100712L — Alternating Strings II in gym 2015 ACM Amman Collegiate Programming Contest

Given a string **S** consists of 0's and 1's only, and given **K**, we define the alternating string is that the string that starts with 0 and then alters 1 then 0... to the end of the string or vice versa starts with 1, for example, `101`

,`01`

,`010`

are alternating strings, while `110`

,`0`

,`01011`

are not.

**1 <= K <= |S| <= 100000**, you are to find the minimum number of cuts you have to make to break the string down into non-alternating strings that each of them has at most **K** digits .

I tried to solve it this way, let `dp[i]`

be the minimum number of partitions that needed to split **S** as the problem states, assuming the indexing starts with **2** being the first character, and **n** is the length of the string, then the answer to the problem will be `dp[n+1]-1`

`alt[i]`

contains the length of the longest alternating string that ends at position `i`

.

Now let `dp[1] = 0`

and start iterating over the string from 2 to n+1, initially `dp[i] = dp[i-1]+1`

that we made a cut at position `i`

then let's look at the longest alternating string in the range `[i-k,i]`

, let this value be `e`

, if e is less than the length of the range `[i-k,i]`

then for sure this range doesn't form an alternating string, so we look up the minimum value of `dp`

in the range `[i-k-1,i-1]`

and update `dp[i]`

with `min(dp[i],minValue+1)`

.

Here's my code, I keep getting WA I tried to figure out where I'm going wrong but no use, I would be so grateful if someone could indicate what's wrong with this algorithm/code .

I didn't read your code but try this test case:

1

5 2

11111

your code prints 1 instead of 2 ,I hope it helps you.

Ya, that's right.

Thank you, I'm trying to fix it now.

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).