{"problem":{"name":"Yet Another Palindrome Partitioning","description":{"content":"We have a string $s$ consisting of lowercase English letters. Snuke is partitioning $s$ into some number of non-empty substrings. Let the subtrings obtained be $s_1$, $s_2$, $...$, $s_N$ from left to ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"code_festival_2017_qualc_d"},"statements":[{"statement_type":"Markdown","content":"We have a string $s$ consisting of lowercase English letters. Snuke is partitioning $s$ into some number of non-empty substrings. Let the subtrings obtained be $s_1$, $s_2$, $...$, $s_N$ from left to right. (Here, $s = s_1 + s_2 + ... + s_N$ holds.) Snuke wants to satisfy the following condition:\n\n*   For each $i$ ($1 \\leq i \\leq N$), it is possible to permute the characters in $s_i$ and obtain a palindrome.\n\nFind the minimum possible value of $N$ when the partition satisfies the condition.\n\n## Constraints\n\n*   $1 \\leq |s| \\leq 2 \\times 10^5$\n*   $s$ consists of lowercase English letters.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$s$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"code_festival_2017_qualc_d","tags":[],"sample_group":[["aabxyyzz","2\n\nThe solution is to partition $s$ as `aabxyyzz` = `aab` + `xyyzz`. Here, `aab` can be permuted to form a palindrome `aba`, and `xyyzz` can be permuted to form a palindrome `zyxyz`."],["byebye","1\n\n`byebye` can be permuted to form a palindrome `byeeyb`."],["abcdefghijklmnopqrstuvwxyz","26"],["abcabcxabcx","3\n\nThe solution is to partition $s$ as `abcabcxabcx` = `a` + `b` + `cabcxabcx`."]],"created_at":"2026-03-03 11:01:14"}}