Candy Necklace

Interview

Time limit1sMemory limit1024 MB

Summary

Given a circular necklace of B and V candies with even length, choose a split into two equal halves that maximizes the number of B's in one half.

Level: Medium4 of 10
Topics: Sliding window, Prefix sum, Array, String
Solved: No attempts yet

Problem

Alice wants to share a candy necklace with Bob. The necklace consists of white candies and blue candies. To be fair, Alice wants to cut the necklace into two parts with the same number of candies in each. However, Alice likes the blue candies much more than the white ones, so she wants to get as many blue candies in her half as possible.

If Alice cuts the necklace optimally, what is the largest number of blue candies she can get in her part?

Input

The input consists of one line with a string describing the necklace. The string consists only of the letters B and V, and has an even total number of letters.

Output

Print one line with an integer, the maximum number of blue candies Alice can get in her part of the necklace.

Constraints

The necklace consists of at most 1000000 candies.

Hint

BBVVBVVVBB has length 10, so Alice must split the necklace into two parts with 5 candies each. The possible parts she can get are BBVVB, BVVBV, VVBVV, VBVVV, BVVVB, VVVBB, VVBBB, VBBBB, BBBBV, BBBVV. She gets the most blue candies by choosing VBBBB or BBBBV, which have $4$ blue candies.

Figure 1. One of two optimal ways to cut in sample case 1

Examples3

Example 1
Input
```
BBVVBVVVBB
```
Expected output
```
4
```
Example 2
Input
```
BVBVBVBV
```
Expected output
```
2
```
Example 3
Input
```
BBVBVVVBBVVBBBVBVVBV
```
Expected output
```
6
```