Alice has a binary string, , of length . She thinks a binary string is beautiful if and only if it doesn't contain thesubstring .
In one step, Alice can change a to a (or vice-versa). Count and print the minimum number of steps needed to make Alice see the string as beautiful.
Input Format
The first line contains an integer, (the length of binary string ).
The second line contains a single binary string, , of length .
The second line contains a single binary string, , of length .
Constraints
- Each character in .
Output Format
Print the minimum number of steps needed to make the string beautiful.
Sample Input 0
7
0101010
Sample Output 0
2
Sample Input 1
5
01100
Sample Output 1
0
Sample Input 2
10
0100101010
Sample Output 2
3
Explanation
Sample Case 0:
In this sample,
The figure below shows a way to get rid of each instance of :
Because we were able to make the string beautiful by changing characters ( and ), we print .
Sample Case 1:
In this sample
The substring does not occur in , so the string is already beautiful and we print .
====================================================
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String B = in.next();
int i = 0, out = 0, next = 0;
if (B.indexOf("010") >= 0) {
while (i < B.length()) {
next = B.indexOf("010", i) + 3;
if (next < i) {
break;
}
i = next;
out++;
}
} else {}
System.out.println(out);
}
}
