Flipping

Interview

Time limit2sMemory limit128 MB

Summary

Given a binary string, find the minimum number of contiguous-segment flips needed to make all characters equal.

Level: Medium4 of 10
Topics: String, Greedy, Math
Solved: No attempts yet

Problem

You are given a binary string S. In one move, choose one or more consecutive characters of S and flip all of them: 0 becomes 1, and 1 becomes 0.

Your goal is to make every character in the string equal.

For instance, let S = 0001100.

If you flip the whole string, it becomes 1110011.
If you then flip the 4th through 5th characters, it becomes 1111111, so two moves are enough.

However, if you flip only the 4th through 5th characters from the start, the string becomes 0000000, so one move is enough.

Given S, find the minimum number of moves needed.

Input

The first line contains a binary string S. The length of S is less than 1,000,000.

Output

Print the minimum number of moves needed to make every character equal.

Examples5

Example 1
Input
```
0001100
```
Expected output
```
1
```
Example 2
Input
```
11111
```
Expected output
```
0
```
Example 3
Input
```
00000001
```
Expected output
```
1
```
Example 4
Input
```
11001100110011000001
```
Expected output
```
4
```
Example 5
Input
```
11101101
```
Expected output
```
2
```