String Exchange

Interview

Time limit2sMemory limit128 MB

Summary

Given a circular string of a's and b's, find the minimum number of swaps to make all a's form one consecutive block.

Level: Medium5 of 10
Topics: Sliding window, String, Greedy, Array
Solved: No attempts yet

Problem

You are given a string containing only a and b. You may swap characters to make all a characters occupy one consecutive block. Find the minimum number of swaps needed.

The string is circular, so the first and last characters are adjacent.

For example, aabbaaabaaba can be rearranged so that all a characters are consecutive with two swaps.

Input

The first line contains a string consisting only of a and b. The length of the string is at most 1,000.

Output

Print the minimum number of swaps needed to make all a characters consecutive.

Examples6

Example 1
Input
```
abababababababa
```
Expected output
```
3
```
Example 2
Input
```
ba
```
Expected output
```
0
```
Example 3
Input
```
aaaabbbbba
```
Expected output
```
0
```
Example 4
Input
```
abab
```
Expected output
```
1
```
Example 5
Input
```
aabbaaabaaba
```
Expected output
```
2
```
Example 6
Input
```
aaaa
```
Expected output
```
0
```