Write an efficient function that checks whether any permutation of an input string is a palindrome.
"civic" should return True
"ivicc" should return True
"civil" should return False
"livci" should return False
"But 'ivicc' isn't a palindrome!"
If you had this thought, read the question again carefully. We're asking if any permutation of the string is a palindrome. Spend some extra time ensuring you fully understand the question before starting. Jumping in with a flawed understanding of the problem doesn't look good in an interview.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
time, since we're making one iteration through the n characters in the string.
Our unpaired_charactersset is the only thing taking up non-constant space. We could say our space cost is as well, since the set of unique characters is less than or equal to n. But we can also look at it this way: there are only so many different characters. How many? The ASCII character set has just 128 different characters (standard english letters and punctuation), while Unicode has 110,000 (supporting several languages and some icons/symbols). We might want to treat our number of possible characters in our character set as another variable k and say our space complexity is . Or we might want to just treat it as a constant, and say our space complexity is .