M. Colour the Banners
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the world of Westeros, the Kingdoms of Westeros were constantly vying for power and control, each represented by a different color on the banners that flew high above their castles. But when a strange and powerful enemy threatened to destroy them all, the lords and ladies of the kingdoms realized that they needed to work together if they were to survive.

To do so, they turned to an ancient and mysterious mage, known by the name IronByte, who was said to have the power to solve any problem. The mage presented them with a strange riddle, stating that they needed to choose the colors of their banners in such a way that there were no adjacent banners with the same colours, or face the consequences.

The problem with that, is that many kingdoms have already installed their banners, and they cannot be altered. The only solution is to set the colours of the banners for the remaining kingdoms so that there will not be a pair of adjacent kingdoms with the same colour.

Now, the banners are represented by a string $$$S$$$ where $$$S_i$$$ is:

  • The colour of the banner of the $$$i^\text{th}$$$ kingdom if $$$S_i$$$ is an uppercase latin character
  • A kingdom without a banner if $$$S_i=.$$$
Also, the banners form a straight line, so the adjecent banners are represented by the pairs $$$(S_i,S_{i+1}).$$$

A final critical problem, is the budget Kingdoms is limited, so they should use as few colours as possible.

Please help them to determine the minimal number of colours they need to solve the riddle, or $$$-1$$$ if they will face imminent destruction.

Input
  • The first line consists of an integer $$$1 \le n \le 10^5,$$$ representing the number of Kingdoms
  • The second line consists of a string $$$S$$$ with length $$$n,$$$ where:
    • $$$S_i\in \{\mathtt{A},\dots,\mathtt{Z}\}$$$ if the banner of the $$$i^\text{th}$$$ kingdom is installed and has as colour $$$S_i$$$
    • $$$.$$$ otherwise if the banner of the $$$i^\text{th}$$$ kingdom is not yet installed.
Output

A single integer $$$n$$$ representing the minimal number of colours, or $$$-1$$$ if it is impossible to have adjacent pairs with different colours.

Examples
Input
5
RG..R
Output
2
Input
5
RG.BG
Output
3