×

# CHEFHPAL - Editorial

Author: Hanlin Ren
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

MEDIUM

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.

# RELATED PROBLEMS:

This question is marked "community wiki".

2★melfice
71829
accept rate: 0%

19.0k348495533

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

(15 Nov '17, 10:34)

 0 Hello please help me to understand this "The tricky case is A=2A=2. We will prove that for N≥9N≥9 the minimum longest palindromic substring length is 4." for N=11,a=2 aaabababbbb=5 aaabaabbbbb=5 aaababbabbb=5 please let me know for which instance it is 4 answered 15 Nov '17, 09:35 24●1●2●7 accept rate: 0% Hello! It is 4 for example for "aabbabaabba", as it is stated in the editorial (to obtain the answer for any N, repeat the string "aabbab" sufficient number of times). What we are trying to prove is that there can be no string for which the maximum palindromic substring has length <4, i.e. 1, 2 or 3. (15 Nov '17, 18:19) melfice2★
 0 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 1★chhekur 23●3 accept rate: 0%
 0 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 46●5 accept rate: 9%
 0 "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 24●1●2●7 accept rate: 0%
 0 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^(L-1) + 1 to 2^L. answered 16 Nov '17, 23:06 2★devsaw 1 accept rate: 0%
 0 Is their any other way than hit and trial to come up with the sequence answered 22 Nov '17, 01:57 2★bhpra 103●6 accept rate: 12%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,480
×2,413
×300
×115
×6

question asked: 13 Nov '17, 06:35

question was seen: 1,697 times

last updated: 22 Nov '17, 01:57