A. Antipalindrome

Codeforces

IDCF981A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings "_kek_", "_abacaba_", "_r_" and "_papicipap_" are palindromes, while the strings "_abb_" and "_iq_" are not. A substring $s[l \ldots r]$ ($1 \leq l \leq r \leq |s|$) of a string $s = s_{1}s_{2} \ldots s_{|s|}$ is the string $s_{l}s_{l + 1} \ldots s_{r}$. Anna does not like palindromes, so she makes her friends call her Ann. She also changes all the words she reads in a similar way. Namely, each word $s$ is changed into its longest substring that is not a palindrome. If all the substrings of $s$ are palindromes, she skips the word at all. Some time ago Ann read the word $s$. What is the word she changed it into? ## Input The first line contains a non-empty string $s$ with length at most $50$ characters, containing lowercase English letters only. ## Output If there is such a substring in $s$ that is not a palindrome, print the maximum length of such a substring. Otherwise print $0$. Note that there can be multiple longest substrings that are not palindromes, but their length is unique. [samples] ## Note "_mew_" is not a palindrome, so the longest substring of it that is not a palindrome, is the string "_mew_" itself. Thus, the answer for the first example is $3$. The string "_uffuw_" is one of the longest non-palindrome substrings (of length $5$) of the string "_wuffuw_", so the answer for the second example is $5$. All substrings of the string "_qqqqqqqq_" consist of equal characters so they are palindromes. This way, there are no non-palindrome substrings. Thus, the answer for the third example is $0$.

如果一个字符串从左到右和从右到左读都相同，则称其为回文串。例如，字符串 "_kek_"、"_abacaba_"、"_r_" 和 "_papicipap_" 是回文串，而字符串 "_abb_" 和 "_iq_" 不是。字符串 $s = s_1 s_2 dots.h s_(| s |)$ 的子串 $s [ l dots.h r ]$（$1 lt.eq l lt.eq r lt.eq | s |$）是字符串 $s_l s_(l + 1) dots.h s_r$。 Anna 不喜欢回文串，因此她让朋友们叫她 Ann。她也会以类似方式修改她阅读的所有单词。具体而言，每个单词 $s$ 会被替换为其最长的非回文子串。如果 $s$ 的所有子串都是回文串，则她会直接跳过该单词。不久前，Ann 读到了单词 $s$。她将其改成了什么单词？第一行包含一个非空字符串 $s$，长度不超过 50 个字符，仅包含小写英文字母。如果 $s$ 中存在非回文子串，请输出其中最长的非回文子串的长度；否则输出 $0$。注意，可能存在多个最长的非回文子串，但它们的长度是唯一的。 "_mew_" 不是回文串，因此其最长的非回文子串就是其本身 "_mew_"。因此，第一个示例的答案是 $3$。字符串 "_uffuw_" 是字符串 "_wuffuw_" 的最长非回文子串之一（长度为 $5$），因此第二个示例的答案是 $5$。字符串 "_qqqqqqqq_" 的所有子串均由相同字符组成，因此都是回文串。因此，不存在非回文子串。故第三个示例的答案是 $0$。 ## Input 第一行包含一个非空字符串 $s$，长度不超过 50 个字符，仅包含小写英文字母。 ## Output 如果 $s$ 中存在非回文子串，请输出其中最长的非回文子串的长度；否则输出 $0$。注意，可能存在多个最长的非回文子串，但它们的长度是唯一的。 [samples] ## Note "_mew_" 不是回文串，因此其最长的非回文子串就是其本身 "_mew_"。因此，第一个示例的答案是 $3$。字符串 "_uffuw_" 是字符串 "_wuffuw_" 的最长非回文子串之一（长度为 $5$），因此第二个示例的答案是 $5$。字符串 "_qqqqqqqq_" 的所有子串均由相同字符组成，因此都是回文串。因此，不存在非回文子串。故第三个示例的答案是 $0$。

**Definitions** Let $ s $ be a string of length $ n $, where $ s = s_1 s_2 \dots s_n $, and $ s_i \in \{a, b, \dots, z\} $ for all $ i \in \{1, \dots, n\} $. Let $ \mathcal{S} = \{ s[l:r] \mid 1 \leq l \leq r \leq n \} $ be the set of all substrings of $ s $, where $ s[l:r] = s_l s_{l+1} \dots s_r $. A substring $ s[l:r] $ is a *palindrome* if $ s[l:r] = \text{reverse}(s[l:r]) $. **Constraints** 1. $ 1 \leq n \leq 50 $ 2. All characters in $ s $ are lowercase English letters. **Objective** Find the maximum length $ L $ such that there exists a substring $ s[l:r] \in \mathcal{S} $ which is **not** a palindrome and $ r - l + 1 = L $. If no such substring exists, output $ 0 $. That is: $$ L = \max \{ r - l + 1 \mid s[l:r] \text{ is not a palindrome} \} $$ If the set $ \{ r - l + 1 \mid s[l:r] \text{ is not a palindrome} \} $ is empty, then $ L = 0 $.

Samples

Input #1

mew

Output #1

Input #2

wuffuw

Output #2

Input #3

qqqqqqqq

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Antipalindrome",
    "description": {
      "content": "A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings \"_kek_\", \"_abacaba_\", \"_r_\" and \"_papicipap_\" are palindromes, while t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF981A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings \"_kek_\", \"_abacaba_\", \"_r_\" and \"_papicipap_\" are palindromes, while t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "如果一个字符串从左到右和从右到左读都相同，则称其为回文串。例如，字符串 \"_kek_\"、\"_abacaba_\"、\"_r_\" 和 \"_papicipap_\" 是回文串，而字符串 \"_abb_\" 和 \"_iq_\" 不是。\n\n字符串 $s = s_1 s_2 dots.h s_(| s |)$ 的子串 $s [ l dots.h r ]$（$1  lt.eq  l  lt.eq  r  lt.eq  |...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string of length $ n $, where $ s = s_1 s_2 \\dots s_n $, and $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \nLet $ \\mathcal{S} = \\{ s[l:r] \\mid 1 \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments