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 .