We are given a string S of length n that consists of zeros and ones. We would like to modify it in such a way that it will not contain the substring
"010". (A substring is a subsequence of consecutive characters.) The only allowed operations is the inversion of individual bits (i.e. replacement of a
'1' with a
'0' or replacement of a
'0' with a
'1'). What is the minimal number of replacements that are needed to modify string S so that it will not contain the substring
The first line contains integer n, i.e. the length of S. The second line contains the string S which consists of zeros and ones.
- 1 \leq n \leq 10^5
Output one number – the minimal number of required operations.
In the above example we may obtain the string
"0001110" by two replacements. It does not contain the substring
- submit and test your solution
- post or read questions and answers about this task