The Problem Statement is :
Bob is given a string. But Bob only likes palindromes, and now wants to partition the string into palindromes. However, after his friends told him his demands are simply exorbitant, Bob has chosen to relax his conditions. He has agreed to rearranging the partitions himself to make palindromes, so is now looking to partition the string into such ’possible’ palindromes. As always, help Bob to find the minimum partitions needed for his demand to be met.
Sample TestCase
Input — aabxyyzz Output-2
Explanation:The string can be partitioned as aab | xyyzz, since these partitions can bere-arranged to aba, yzxzy, both of which are palindromes
Input — abcdefghijklmnopqrstuvwxyz Output-26
Can any explain how one should approach such problems?
As long as you have a substring where there is at most one letter that appears an odd number of times you can rearrange the letters to form a palindrome. This suggest a greedy O(n2) solution, start at 0 walk right and find the largest r such that the substring from [0,r] contains at most 1 letter that appears an odd number of times. Then move to r+1 and repeat. It feels like the greedy approach is optimal but you might want to prove it. There are probably some additional insights that can speed up this approach to O(n) or
.
This greedy strategy is in fact not optimal. Consider this counter-example: abcabcxabcx . According to your strategy, you should first extract the partition 'abcabcx', and then you are left with 'a', 'b', 'c' and 'x', a total of 5 partitions, where the optimal solution is to form the partitions 'a', 'b', 'cabcxabcx'. This example is from the problem statement of the problem referenced below by the other comment.
Interesting.
This problem has already been made and can be solved with time complexity O (N).
https://beta.atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d