Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2019
Beer Mugs
mugs.c, mugs.cpp, Mugs.java, mugs.py
Damian is a beer mug collector. His collection fills most of the shelves in his vintage wooden
cabinet where all mugs are proudly displayed. The mugs are of various brands. There might be,
and often are, more mugs of the same brand in the collection.
Mugs on a shelf in Damian's collection always form a single symmetric row. Specifically, the
symmetry of the row means that the sequence of particular mug brands in the row is the same
when the mugs are being admired one by one from left to right and when the mugs are being
admired one by one from right to left. There is still one empty shelf in the cabinet and Damian
looks for an opportunity to fill it with a new set of mugs.
The widely recognized Mastodon brewery (admired for its Woolly Mammoth beer) organizes
annually the so-called beer season. Participants of the season are engaged in daily beer brewing
activities and are rewarded each day by a special collector mug. Each day in the season is
assigned a particular mug brand. The mug brands for all days in the season are known in
advance, some brands may appear repeatedly in the season.
A participant may subscribe for the whole season or just for a part of the season. However, all
days of his or her participation have to be in one uninterrupted sequence of days, a participant
cannot leave the season and then come back again after some days of absence.
Damian is keen to take part in the beer season. He decided that the set of mugs he brings home
should be suited for his display without adding or removing any mug, and that the set should
be as big as possible.
Given the list of mug brands provided by the brewery for all days in the beer season, find the size
of the biggest set of mugs suitable for Damian's display which can be obtained by subscribing
to some appropriately chosen part of the beer season.
Input Specification
The first input line contains integer N (1 < N ≤ 300 000) the number of days in the brewery
beer season. The next line contains N characters representing the list of all beer mug brands
offered in the season, day by day. The list is naturally ordered from the first day to the last
day of the season. Each brand is coded by a single lower case letter, from 'a' to 't'. The list
contains no blanks.
Output Specification
Print a single integer representing the size of the biggest set of mugs which Damian can bring
home from the brewery beer season and which is suitable, without changes, for his collection
display.
Sample Input 1
Output for Sample Input 1
6
6
abcabc
Sample Input 2
Output for Sample Input 2
20
7
ghjahjghsajdjhlfslja
Sample Input 3
Output for Sample Input 3
12
9
aabbccddabcd
