Hello there, <br /> <br />↵
Several days ago I came across this problem [100712L — Alternating Strings II](http://mirror.codeforces.com/gym/100712/attachments) in gym [2015 ACM Amman Collegiate Programming Contest](http://mirror.codeforces.com/gym/100712) <br /> <br />↵
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. <br /> <br />↵
**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 . <br />↵
↵
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` <br />↵
↵
`alt[i]` contains the length of the longest alternating string that ends at position `i`. <br />↵
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)` . <br /> <br />↵
Here's my [code](http://pastebin.com/BUf3PsSV), 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 .
Several days ago I came across this problem [100712L — Alternating Strings II](http://mirror.codeforces.com/gym/100712/attachments) in gym [2015 ACM Amman Collegiate Programming Contest](http://mirror.codeforces.com/gym/100712) <br /> <br />↵
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. <br /> <br />↵
**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 . <br />↵
↵
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` <br />↵
↵
`alt[i]` contains the length of the longest alternating string that ends at position `i`. <br />↵
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)` . <br /> <br />↵
Here's my [code](http://pastebin.com/BUf3PsSV), 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 .
