I. Mirrored String II

Codeforces

IDCF10135I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Note: this is a harder version of Mirrored string I. The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings. A mirrored string is a palindrome string that will not change if you view it on a mirror. Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome. e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not. A palindrome is a string that is read the same forwards and backwards. Given a string S of length N, help the gorillas by printing the length of the longest mirrored substring that can be made from string S. A substring is a (possibly empty) string of characters that is contained in another string S. e.g. "Hell" is a substring of "Hello". The first line of input is T – the number of test cases. Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters. For each test case, output on a line a single integer - the length of the longest mirrored substring that can be made from string S. ## Input The first line of input is T – the number of test cases.Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters. ## Output For each test case, output on a line a single integer - the length of the longest mirrored substring that can be made from string S. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. Let $ \mathcal{M} = \{A, H, I, M, O, T, U, V, W, X, Y\} $ be the set of mirrored characters. For each test case, let $ S $ be a string of length $ N $, where $ S \in \Sigma^* $ and $ \Sigma = \{A, B, \dots, Z\} $. **Constraints** 1. $ 1 \le T \le \text{unknown (implied by input)} $ 2. For each string $ S $: - $ 1 \le |S| \le 1000 $ - $ S $ contains only uppercase English letters. **Objective** For each string $ S $, find the maximum length $ L $ such that there exists a substring $ S[i:j] $ (with $ 1 \le i \le j \le |S| $) satisfying: 1. $ S[i:j] $ is a palindrome: $ S[i+k] = S[j-k] $ for all $ k = 0, 1, \dots, \left\lfloor \frac{j-i}{2} \right\rfloor $, 2. Every character in $ S[i:j] $ belongs to $ \mathcal{M} $. Output $ L = \max \{ |S[i:j]| \mid S[i:j] \text{ is a mirrored substring} \} $.

API Response (JSON)

{
  "problem": {
    "name": "I. Mirrored String II",
    "description": {
      "content": "Note: this is a harder version of Mirrored string I. The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10135I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Note: this is a harder version of Mirrored string I.\n\nThe gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ \\mathcal{M} = \\{A, H, I, M, O, T, U, V, W, X, Y\\} $ be the set of mirrored characters.  \nFor each test case, let $ S $ b...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments