You are given a string S consisting of letters 'a' and/or 'b'. A block is a consecutive fragment of S composed of the same letters and surrounded by different letters or string endings. For example, S = "abbabbaaa" has five blocks: "a", "bb", "a", "bb" and "aaa".

What is the minimum number of additional letters needed to obtain a string

containing blocks of equal lengths? Letters can be added only at the

beginning or at the end of an existing block.

Write a function:

class Solution ( public int solution(String 5); }

that, given a string S of length N, returns the minimum number of additional letters needed to obtain a string containing blocks of equal lengths.

Examples:

1. Given S="babaa", the function should return 3. There are four blocks: "b", "a", "b", "aa". One letter each should be added to the first, second and third blocks, therefore obtaining a string "bbaabbaa", in which every block is of equal length.

2. Given S="bbbab", the function should return 4. Two letters each should be added to the second and third blocks, therefore obtaining a string "bbbaaabbb", in which every block is of equal length.

3. Given S="bbbaaabbb", the function should return 0. All blocks are already of equal lengths.

Write an efficient algorithm for the following assumptions:

. N is an integer within the range [1..40,000];

• string S consists only of the characters "a" and/or "b".