Palindrome Permutation - Python Solution

1. Introduction

The "Palindrome Permutation" problem combines concepts of string manipulation, palindromes, and permutation theory. It explores whether the letters of a given string can be rearranged to form a palindrome. This problem is prevalent in computer science, particularly in areas focusing on algorithms for string processing and combinatorics.

Problem

Given a string, determine if a permutation of the string could form a palindrome. A palindrome is a word or phrase that reads the same backward as forward. The solution should identify whether the characters of the string can be rearranged to achieve this property.

2. Solution Steps

1. Use a hash set to store characters.

2. Iterate through each character in the string.

3. For each character, if it's not in the set, add it; if it's already in the set, remove it.

4. By the end of the iteration, check the size of the set.

5. If the size is 0 or 1, the string can form a palindrome (since the middle character in a palindrome can be unique).

6. If the size is greater than 1, it cannot form a palindrome.

3. Code Program

def canPermutePalindrome(s):
    charSet = set()
    for char in s:
        if char in charSet:
            charSet.remove(char)
        else:
            charSet.add(char)
    return len(charSet) <= 1

# Example Usage
print(canPermutePalindrome("code"))  # Output: False
print(canPermutePalindrome("aab"))   # Output: True
print(canPermutePalindrome("carerac"))  # Output: True

Output:

False
True
True

Explanation:

1. HashSet for Character Tracking: Efficiently tracks the occurrence of each character.

2. Character Addition and Removal: Adds/removes characters to/from the set based on their occurrence.

3. Final Check: If the set has 0 or 1 characters, a palindrome permutation is possible.

4. Odd Characters: Allows for one unique character, which can be the center of a palindrome.

5. Time Complexity: Achieves O(n) time complexity, where n is the length of the string.

6. Practical Use Case: Useful in text analysis and cryptography where palindrome properties are of interest.