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,
010 are alternating strings, while
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
alt[i] contains the length of the longest alternating string that ends at position
dp = 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
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 .