String is Palindromable if any one combination is palindrome.

Question

Let's say you are given a string. You can get many strings (combination) out of the given original string if you rearrange characters of original string.

String is Palindromable if any one combination is palindrome.

Example 1:

Original String: NINIT

Combinations: NINIT, NNIIT,IINNT,ININT,IITNN,NITIN,INTIN,INTNI,NTNII,NNTII and so on

Original string is  Palindromable because two palindrome can be made out of it.

Example 2:

Original String: NINNIT

Combinations: NINITN, NNINIT,IINNNT,INNINT,INITNN,NNITIN,INTNIN,INTNIN,NTNINI,NNTINI and so on

Original string is NOT Palindromable because NO palindrome can be made out of it.

Question:

Write a program to check it given string is Palindromable or not. (please note this is not a question to check if string is palindrome or not).

Complexity of the program should be less then O(n) what is using no or one loop 

Answer 1

to be palindromable, check the string size.

if even number -palindromable if each letter in the string has an even number of duplicates

if odd - palindromable if each letter in the string has an even number of duplicates and one is odd.

you can use one loop method to check number of duplicates which you can call for both even and odd options.

haven't the time to write the code... but this is a head start.