Solution Explanation: Palindrome Permutation

The problem asks whether a given string can be rearranged to form a palindrome. A string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. All other characters must appear an even number of times. This is because a palindrome reads the same forwards and backward.

Approach: Character Counting

The most efficient approach involves counting the occurrences of each character in the string. We can then check if the count of characters with odd occurrences is less than or equal to 1.

Algorithm:

1. Count Character Frequencies: Iterate through the string and count the frequency of each character. A hash table (or dictionary in Python) is ideal for this, providing O(1) average-case lookup time.

2. Check Odd Counts: Iterate through the character frequencies. Count the number of characters with odd frequencies.

3. Return Result: If the count of characters with odd frequencies is less than 2, return true; otherwise, return false.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the string. This is because we iterate through the string once to count character frequencies and then iterate through the frequency counts (which will be at most the size of the alphabet, a constant).

• Space Complexity: O(1) in the average case. We use a hash table (or equivalent data structure) to store character frequencies. In this specific problem, the hash table will store at most 26 entries (for lowercase English letters), making the space complexity effectively constant. In the worst case (if the hash table implementation uses dynamic resizing and the string contains a lot of unique characters), space complexity can reach O(n), but for practical purposes, it is considered O(1).

Code Implementation (Multiple Languages)

The following code implements the solution in several languages:

Python:

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

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> charCounts = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
        }
        int oddCounts = 0;
        for (int count : charCounts.values()) {
            if (count % 2 != 0) {
                oddCounts++;
            }
        }
        return oddCounts <= 1;
    }
}

C++:

#include <iostream>
#include <string>
#include <map>
 
class Solution {
public:
    bool canPermutePalindrome(std::string s) {
        std::map<char, int> charCounts;
        for (char c : s) {
            charCounts[c]++;
        }
        int oddCounts = 0;
        for (auto const& [key, val] : charCounts) {
            if (val % 2 != 0) {
                oddCounts++;
            }
        }
        return oddCounts <= 1;
    }
};

JavaScript:

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function(s) {
    const charCounts = {};
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        charCounts[char] = (charCounts[char] || 0) + 1;
    }
    let oddCounts = 0;
    for (const count of Object.values(charCounts)) {
        if (count % 2 !== 0) {
            oddCounts++;
        }
    }
    return oddCounts <= 1;
};

These code snippets all follow the same algorithmic approach, varying only in their syntax and use of built-in data structures. They all achieve the O(n) time complexity and O(1) average-case space complexity as described above.