You have non-quadratic alternatives. Sort the string and then start iterating through the characters. Keep a boolean for if you've ever seen a character an odd number of times. The first time you get an odd count for a given character, set the bool to true. The second time, you see the bool is already true so you know the word isn't a palindrome and can immediately return false. If you get to the end of the string without hitting that condition, return true.
Yes, that's what I had in mind when I wrote "I may sort the word before hand".
Emphasis on "may", though: for small enough words, sorting may very well slow us down, so it really depends on the data: are we processing long words, or lots of small words?
