| IX MaratonUSP Freshman Contest |
|---|
| Finished |
As part of the celebrations for the 90th anniversary of its creation, the Union of the Solar Planets (USP) decided to pay tribute to Saturn. The tribute will also serve as a symbol of the peace treaty to be signed between the USP and the kingdom of Saturn, ruled by the malevolent monarch Mori.
When consulted about the tribute, the malevolent monarch Mori ordered the construction of a gigantic necklace of asteroids for his planet. After all, what good are rings without a necklace? Furthermore, as if the task were not already fantastical enough, to symbolize the ideals of freedom and equality of the treaty, each asteroid must be either amber (a) or blue (b), coincidentally the colors of the USP flag.
To carry out this astronomically proportioned challenge, two space jewelers with vast experience in colorful asteroids, Rafael and Pedro, were summoned. The task proved even more difficult than the jewelers expected, but with little time remaining before the deadline, they managed to complete the construction of a string with $$$n$$$ amber and blue asteroids, without a specific order.
Only the final step of joining the two ends of the string remained when the monarch Mori maliciously machinated yet another restriction on the tribute: now, one half of the necklace must consist only of amber asteroids and the other half only of blue asteroids. Considering the tight deadline and the colossal proportions of the project, the jewelers would not be able to construct a new string in time. Then an idea emerged: remove a contiguous segment of the string (possibly the entire string) and join the two ends of this segment to form a necklace that meets the new restrictions.
Now Rafael and Pedro need to assess the feasibility of this plan and have asked for your help to determine the maximum size (in number of asteroids) of a necklace that can be created with this technique, also meeting the restrictions that the malevolent monarch Mori maliciously machinated. Note that a necklace of size zero is also valid according to the restrictions, and that the initial string is not circular, meaning the first and last asteroids are not initially connected to each other.
The first line of input contains an integer $$$1 \leq n \leq 2\cdot 10^5$$$ — the amount of asteroids in the string.
The second line of input contains a string of size $$$n$$$ with characters equal to 'a' and 'b' — the sequence of colors of asteroids in the string.
Print a single line containing an integer — the size of the largest necklace that can be obtained from the string following the described technique.
9babbbaabb
6
6bababa
2
7baaaabb
4
1a
0
In the first example, valid necklaces of different sizes can be obtained, as shown in the figure below, but the largest one is the necklace obtained from the segment "abbbaa", with a size of six.
In the second example, only valid necklaces of size zero or two can be obtained.
In the third example, the largest valid necklace that can be obtained has a size of four, from the segment "aabb" at the end of the string.
In the fourth example, no valid necklace larger than size zero can be obtained.
