PROBLEM LINK:
Author: Hanlin Ren
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Brute force
PROBLEM:
Using only A first latin letters, construct a string of length N whose longest palindromic substring is as short as possible; also output this length;
QUICK EXPLANATION:
Handle easy cases A=1 (unique answer) and A>2 (the prefix of the infinite string \underbrace{abc}_{\text{period}}abcabcabc\ldots contains only single-letter palindromes). When A=2, for N\le 8 find the answer via brute force; for N>8, the minimum palindrome substring length is 4, and one of the possible answers is the prefix of the infinite string \underbrace{aabbab}_{\text{period}}~aabbab~aabbab~aabbab~\ldots.
EXPLANATION:
For A=1, the only possible string is \underbrace{aaa\ldots a}_{N\text{ times}}, and the length of its longest palindromic substring is N.
For A>2, take the prefix of the string \underbrace{abc}_{\text{period}}abcabcabc\ldots to construct the answer that contains only one-letter palindromes. This infinite string has no palindromic substrings of longer length: if the first and the last characters of its substring (longer than 2) are equal, then its second from the beginning and second from the ending characters differ.
The tricky case is A=2. We will prove that for N\ge 9 the minimum longest palindromic substring length is 4.
First, let’s prove that for strings of length N\ge 9 there always exists a palindromic substring of length at least 4. Let’s call consecutive equal characters a block. For example, string aabbaba consists of 5 blocks: aa,bb,a,b,a. If one of the blocks is 4 characters or longer, the substring is found. Otherwise, all blocks are of length \le 3. Whenever some block of length 2 or 3 is not the first nor the last block in the string, we have a palindromic substring of length 4 and 5 respectively. If this is not the case, all blocks, except maybe the leftmost and rightmost ones, are of length 1. As the length of the string is at least 9 and the lengths of the leftmost and rightmost blocks are at most 6 there are at least 3 one-letter blocks which are not leftmost and rightmost. Then there exists a palindromic substring ababa or babab of length 5, formed by these blocks and their neighbours, if needed.
It is easy to see that the prefixes of the infinite string \underbrace{aabbab}_{\text{period}}~aabbab~aabbab~aabbab~\ldots contain no palindromic substrings of length greater than 4: to verify this, consider each character as a candidate for an odd-length palindromic substring center, and each pair of adjacent characters as a candidate for an even-length palindromic substring center. Both cases quickly lead to the contradiction.
For A=2, N\le 8, find the answers by brute force in O(2^N\cdot n^3): for each of the possible 2^N binary strings, check whether each of the O(N^2) substrings is palindromic in O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
