Just [[currentUser.getNumFreeQuestionsLeft()]] No more free questions left!Upgrade Now
Write an efficient function that checks whether any permutation of an input string is a palindrome.
You can assume the input string only contains lowercase letters.
"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 can do this in time.
time, since we're making one iteration through the n characters in the string.
Our unpairedCharacters hash set 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 hash 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 .