Code Implementation

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter
        count = Counter(s)
        odd_count = sum(1 for v in count.values() if v % 2 != 0)
        return odd_count <= 1
      

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        int odd = 0;
        for (auto &kv : count) {
            if (kv.second % 2 != 0) odd++;
        }
        return odd <= 1;
    }
};
      

class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] count = new int[128];
        for (char c : s.toCharArray()) count[c]++;
        int odd = 0;
        for (int v : count) {
            if (v % 2 != 0) odd++;
        }
        return odd <= 1;
    }
}
      

var canPermutePalindrome = function(s) {
    const count = {};
    for (let c of s) {
        count[c] = (count[c] || 0) + 1;
    }
    let odd = 0;
    for (let key in count) {
        if (count[key] % 2 !== 0) odd++;
    }
    return odd <= 1;
};
      

Problem Description

Given a string s, determine if a permutation of s could form a palindrome. You do not need to return the actual palindrome, just whether it is possible to rearrange the characters of s so that the result is a palindrome string.

Constraints:

• All characters are lowercase or uppercase English letters.
• There is only one input string s.
• Each character can be used only as many times as it appears in s.
• You need to check if any permutation is a palindrome, not just the original order.

Thought Process

The first instinct might be to try generating all possible permutations of s and check if any of them is a palindrome. However, that would be highly inefficient since the number of permutations grows factorially with the length of the string.

Instead, let's consider what makes a string a palindrome. A palindrome reads the same forwards and backwards. For a string to be rearranged into a palindrome:

• If the string length is even, every character must appear an even number of times.
• If the string length is odd, only one character can appear an odd number of times (it will be the middle character), and all others must appear an even number of times.

Solution Approach

Here is how we can solve the problem efficiently:

1. Count Character Frequencies: Use a hash map (dictionary) to count how many times each character appears in s. This allows us to quickly look up and update counts as we iterate through the string.
2. Check Odd Counts: Iterate over the frequency map and count how many characters have an odd number of occurrences.
3. Decision: If the number of characters with odd counts is more than one, it's impossible to form a palindrome permutation. If it's zero or one, it is possible.

This approach is efficient because:

• Counting characters is O(n), where n is the length of the string.
• Checking the counts is O(1) for a fixed alphabet size, or O(k) where k is the number of distinct characters.

Example Walkthrough

Let's walk through an example with s = "aabbcc":

• Count the frequency of each character:
  • 'a': 2
  • 'b': 2
  • 'c': 2
• Check how many characters have an odd count:
  • All characters have even counts (0 odd counts).
• Since there are 0 characters with odd counts, a palindrome permutation is possible (e.g., "abccba").

Another example: s = "aabbc"

• Frequencies:
  • 'a': 2
  • 'b': 2
  • 'c': 1
• 'c' has an odd count (1 odd count).
• Since there is only one odd count, a palindrome permutation is still possible (e.g., "abcba").

• Frequencies:
  • 'a': 1
  • 'b': 1
  • 'c': 1
• There are 3 odd counts. Since more than one character has an odd count, it's impossible to form a palindrome permutation.

Time and Space Complexity

Brute-force approach:

• Generate all permutations: O(n!) time, where n is the length of the string.
• Space: O(n!) for storing permutations.

• Counting frequencies: O(n) time.
• Checking odd counts: O(k) time, where k is the number of unique characters (at most 26 for lowercase English letters).
• Total time: O(n).
• Space: O(k) for the hash map or array.

Summary

To determine if a string can be permuted into a palindrome, we simply count how many characters have odd frequencies. If there is more than one such character, it's impossible; otherwise, it is possible. This insight allows us to solve the problem in linear time and space, making the solution both elegant and efficient.