Palindrome Permutation - Leetcode Solution

Problem: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

Example: Input: "tact coa" Output: True (permutations: "taco cat", "atco cta", etc.)

Solution: To check if a string is a permutation of a palindrome, we need to count how many times each character appears in the string. We don't need to actually generate all permutations of the string to solve this problem.

We can follow these steps to solve the problem:

1. Convert the input string to all lowercase characters and remove all spaces.

2. Iterate through each character in the modified string and count its frequency.

3. If the count of more than one character is an odd number, return False as it is not possible for a palindrome to be formed.

4. If all the character count is an even number, return True as the permutation can be arranged to form a palindrome.

5. If only one character count is an odd number, return True as it can be placed in the middle of the palindrome.

Code:

def is_palindrome_permutation(s): s = s.lower().replace(" ","") char_freq = {} odd_count = 0

for char in s:
    if char not in char_freq:
        char_freq[char] = 1
    else:
        char_freq[char] += 1

for count in char_freq.values():
    if count % 2 != 0:
        odd_count += 1
    if odd_count > 1:
        return False

return True

Explanation: We take the input string "tact coa" and modify it to "tactcoa" by converting it to lowercase and removing all spaces. Then we iterate through each character in the modified string and count its frequency using a dictionary.

We maintain an odd_count variable to check for the count of more than one character with an odd frequency. If the count of more than one character with an odd frequency is greater than 1, it is not possible to form a palindrome and we return False.

If all the characters have an even frequency, we can form a permutation to form a palindrome and we return True. If only one character has an odd frequency, it can be placed in the middle of the palindrome and we can form a palindrome.

1