{"problem":{"name":"Half Palindromes","description":{"content":"You are given a string $S$ consisting of lowercase letters. For each contiguous substring of $S$ (there are $|S|(|S|+1)/2$ such substrings), solve the following problem, and compute the sum of the ans","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"1202Contest_e"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ consisting of lowercase letters. For each contiguous substring of $S$ (there are $|S|(|S|+1)/2$ such substrings), solve the following problem, and compute the sum of the answers.\nProblem: You are given a string $T$ consisting of lowercase letters. Compute the minimum possible length of a string that can be obtained from $T$ by repeatedly applying the following operation an arbitrary number of times.\n\n*   Take a prefix of $T$ that is a palindrome of odd length. Let the length be $2k+1$. Remove the first $k$ letters of $T$.\n\n## Constraints\n\n*   $1\\leq |S|\\leq 10^6$\n*   $S$ consists of lowercase letters.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"1202Contest_e","tags":[],"sample_group":[["abab","16\n\nIf $T$ is `a` or `b`, the answer is $1$.\nIf $T$ is `ab` or `ba`, the answer is $2$.\nIf $T$ is `aba` or `bab`, applying the operation with $k=1$ once is optimal, and the answer is $2$.\nIf $T$ is `abab`, applying the operation with $k=1$ twice is optimal, and the answer is $2$.\nTherefore, the whole answer is $1\\times 4 + 2\\times 3 + 2\\times 2 + 2\\times 1 = 16$."],["abacaba","67"],["tabatadebatabata","739"]],"created_at":"2026-03-03 11:01:13"}}