Palindrome Permutation - CPP Solution

1. Introduction

In this blog post, we'll explore a fascinating string processing problem called "Palindrome Permutation". This problem involves determining whether a permutation of a given string can form a palindrome, showcasing the use of hash tables and character count in C++.

Problem

Given a string, check if it can be rearranged to form a palindrome. A palindrome is a word or phrase that reads the same backward as forward, disregarding spaces, punctuation, and capitalization.

2. Solution Steps

1. Count the frequency of each character in the string.

2. Check the counts of the characters:

- For strings of even length, all characters must have even counts.

- For strings of odd length, only one character can have an odd count.

3. Use a hash table to store the frequency of characters.

4. Iterate through the hash table to check the counts according to the above rules.

5. Return true if the conditions for a palindrome are met, false otherwise.

3. Code Program

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to check if a string can be rearranged to form a palindrome
bool canPermutePalindrome(string s) {
    unordered_map<char, int> charCount;
    int oddCount = 0;

    // Count the frequency of each character
    for (char c : s) {
        charCount[c]++;
    }

    // Check the counts of characters
    for (auto &pair : charCount) {
        if (pair.second % 2 != 0) {
            oddCount++;
        }
    }

    // For palindrome, odd count should be 0 or 1
    return oddCount <= 1;
}

int main() {
    string s = "tactcoa";
    cout << "Can form palindrome: " << canPermutePalindrome(s) << endl;
    return 0;
}

Output:

Can form palindrome: 1

Explanation:

1. The input string "tactcoa" is evaluated to see if its characters can form a palindrome.

2. The frequency of each character is counted, e.g., 't': 2, 'a': 2, 'c': 2, 'o': 1.

3. The function checks that at most one character ('o' in this case) has an odd count.

4. Since the conditions for forming a palindrome are met (only one character with an odd count), the function returns true (represented as 1).

5. This approach efficiently determines whether a string's characters can be rearranged to form a palindrome by using character count and frequency analysis.