Beer Mugs
InterviewTime limit2sMemory limit512 MB
Given a string of N characters over 20 brands, find the longest substring that is a palindrome after permuting it freely.
- Level
Medium7 of 10
- Topics
- Bit manipulation, Hash map, Prefix sum, String matching
- Solved
- No attempts yet
Problem
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. A row is symmetric when the sequence of mug brands is the same whether the mugs are admired one by one from left to right or one by one from right to left. There is still one empty shelf in the cabinet, and Damian looks for a chance to fill it with a new set of mugs.
The widely known Mastodon brewery (admired for its Woolly Mammoth beer) organizes the so-called beer season every year. Participants in the season brew beer every day and are rewarded each day with a special collector mug. Each day of the season is assigned a particular mug brand. The mug brands for all days of the season are known in advance, and some brands may appear repeatedly during the season.
A participant may subscribe for the whole season or only for part of it. However, all days of participation must form one uninterrupted sequence of days. A participant cannot leave the season and come back after some days of absence.
Damian wants to take part in the beer season. He decided that the set of mugs he brings home should suit his display without adding or removing any mug, and that the set should be as big as possible.
Given the list of mug brands the brewery provides for all days of the beer season, find the size of the biggest set of mugs suitable for Damian's display that he can obtain by subscribing to some appropriately chosen part of the beer season.
Input
The first input line contains the 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 ordered naturally from the first day to the last day of the season. Each brand is coded by a single lowercase letter, from 'a' to 't'. The list contains no blanks.
Output
Print a single integer representing the size of the biggest set of mugs that Damian can bring home from the brewery beer season and that is suitable, without changes, for his collection display.