Distinct lengths of runs of zeros

Interview

Time limit1sMemory limit1024 MB

Summary

Given a binary string, count how many distinct lengths appear among its maximal runs of consecutive zeros.

Level: Easy3 of 10
Topics: String, Simulation, Hash map, Implementation
Solved: No attempts yet

Problem

Consider a string of zeros and ones. In such a string, zeros can occur in consecutive substrings, for example 00010001011001. This example has 4 runs of consecutive zeros: 000, 000, 0, and 00.

Write a program zero that reads a string of zeros and ones and finds how many distinct lengths occur among the runs of consecutive zeros.

Input

A single string consisting only of 0 and 1, with length at most 10 000 characters.

Output

A single integer equal to the required count.

Examples4

Example 1
Input
```
0000
```
Expected output
```
1
```
Example 2
Input
```
1001001
```
Expected output
```
1
```
Example 3
Input
```
111
```
Expected output
```
0
```
Example 4
Input
```
1001000
```
Expected output
```
2
```