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.

Examples:

  • "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 can do this in time.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

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 unpairedCharacters 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 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 .

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

RUN
Code execution powered by Qualified.io

. . .