{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq |s| \\leq 2 \\times 10^5$\n*   $s$ consists of lowercase English letters."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$s$"},{"iden":"sample input 1","content":"aabxyyzz"},{"iden":"sample output 1","content":"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`."},{"iden":"sample input 2","content":"byebye"},{"iden":"sample output 2","content":"1\n\n`byebye` can be permuted to form a palindrome `byeeyb`."},{"iden":"sample input 3","content":"abcdefghijklmnopqrstuvwxyz"},{"iden":"sample output 3","content":"26"},{"iden":"sample input 4","content":"abcabcxabcx"},{"iden":"sample output 4","content":"3\n\nThe solution is to partition $s$ as `abcabcxabcx` = `a` + `b` + `cabcxabcx`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}