Palindrome Permutation

Question

Write a function isPalindromePermutation that takes in a string and returns true if any permutation of the string could be a palindrome, and false otherwise.

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Permutation is the rearrangement of characters.

Example

isPalindromePermutation("tactcoa")

Output:

True

Explanation

To solve this problem, we can follow these steps:

1. Initialize an empty dictionary char_count.
2. Iterate through each character c in the given string:
   • If c is already a key in char_count, increment its count by 1.
   • Otherwise, add c as a key to char_count with the value 1.
3. Initialize a variable odd_count to 0.
4. Iterate through each value in char_count:
   • If the value is odd, increment odd_count by 1.
   • If odd_count becomes greater than 1, return False.
5. Return True if the function has not returned False by this point.

In the given example, the given string is "tactcoa".

Iteration 1:

char_count = {}, odd_count = 0

• "t" is not in char_count, so add it with count 1: char_count = {"t": 1}, odd_count = 0

Iteration 2:

char_count = {"t": 1}, odd_count = 0

• "a" is not in char_count, so add it with count 1: char_count = {"t": 1, "a": 1}, odd_count = 0

Iteration 3:

char_count = {"t": 1, "a": 1}, odd_count = 0

• "c" is not in char_count, so add it with count 1: char_count = {"t": 1, "a": 1, "c": 1}, odd_count = 0

Iteration 4:

char_count = {"t": 1, "a": 1, "c": 1}, odd_count = 0

• "t" is already in char_count with count 1, so increment its count by 1: char_count = {"t": 2, "a": 1, "c": 1}, odd_count = 0

Iteration 5:

char_count = {"t": 2, "a": 1, "c": 1}, odd_count = 0

• "c" is already in char_count with count 1, so increment its count by 1: char_count = {"t": 2, "a": 1, "c": 2}, odd_count = 0

Iteration 6:

char_count = {"t": 2, "a": 1, "c": 2}, odd_count = 0

• "o" is not in char_count, so add it with count 1: char_count = {"t": 2, "a": 1, "c": 2, "o": 1}, odd_count = 0

Iteration 7:

char_count = {"t": 2, "a": 1, "c": 2, "o": 1}, odd_count = 0

• "a" is already in char_count with count 1, so increment its count by 1: char_count = {"t": 2, "a": 2, "c": 2, "o": 1}, odd_count = 0

At this point, we have iterated through all the characters in the input string.

Since there are no more characters remaining in the string, we can conclude that any permutation of the given string "tactcoa" can be a palindrome. Therefore, the function should return True.