PROBLEM LINK:Author: Hanlin Ren 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 singleletter 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 oneletter 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$ oneletter blocks which are not leftmost and rightmost. Then there exists a palindromic substring 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 oddlength palindromic substring center, and each pair of adjacent characters as a candidate for an evenlength 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 13 Nov '17, 06:35

You should make it like that for N=11 A=2 aababbaabab Here the length of longest palindromic substring is 4 You can repeat the aababb sequence as many times you want always you will get length is 4 answered 15 Nov '17, 10:29

Superb problem, I personally feel that this is the best problem in November Challenge ignoring the prerequisites of other problems and concentrating on just the thinking capacity of the problem. Problems like this increase the quality of the contests. Thumbs up to setter. answered 15 Nov '17, 14:20

"For A=2,N≤8A=2,N≤8, find the answers by brute force in O(2N⋅n3)O(2N⋅n3): for each of the possible 2N2N binary strings, check whether each of the O(N2)O(N2) substrings is palindromic in O(N)O(N)." For a=2 and n<=8 my solution is O(n) answered 16 Nov '17, 11:51

The solution to this problem is not obvious at all. I got a partial output correct for N<=10. The mistake I did was that I generated a string with shortest longest palindromic substring as L for string lengths 2^(L1) + 1 to 2^L. answered 16 Nov '17, 23:06

Is their any other way than hit and trial to come up with the sequence answered 22 Nov '17, 01:57

Is the difficulty correct? It by no means is medium problem :/