1. Brute Force

Intuition

A string can form a palindrome if at most one character has an odd count. In a palindrome, characters mirror around the center, so pairs must exist for every character except possibly one in the middle.

The brute force approach counts occurrences of each possible ASCII character by iterating through the string for each character code. If more than one character has an odd frequency, no palindrome permutation is possible.

Algorithm

1. For each ASCII character (0 to 127), count how many times it appears in the string.
2. Track how many characters have odd counts.
3. If we find more than one character with an odd count, return false early.
4. Return true if at most one character has an odd frequency.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        count = 0
        for i in range(128):  # For all ASCII characters
            if count > 1:
                break
            ct = 0
            for j in range(len(s)):
                if s[j] == chr(i):  # Comparing with ASCII character
                    ct += 1
            count += ct % 2
        return count <= 1

Time & Space Complexity

• Time complexity: $O(n)$
  • If we generalize the solution to handle any Unicode character (no hardcoding): $O(k \cdot n)$.
    $O(n^2)$ In the worst case, if all characters are unique $(k = n)$
• Space complexity: $O(1)$ If the we assume the input contains only ASCII characters.
  • $O(1)$ If the implementation is modiifed to handle Unicode characters.

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

---

2. Using HashMap

Intuition

Instead of iterating through all possible ASCII characters, we can use a hash map to only track characters that actually appear in the string. This is more efficient when the string uses a small subset of the character set.

We count the frequency of each character, then check how many have odd counts. The palindrome condition remains the same: at most one odd frequency.

Algorithm

1. Use a hash map to store the frequency of each character in the string.
2. Iterate through the string once, incrementing counts for each character.
3. Count how many characters have odd frequencies.
4. Return true if the odd count is at most 1.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter

        count = Counter(s)
        odds = sum(val % 2 for val in count.values())
        return odds <= 1

Time & Space Complexity

• Time complexity: $O(n)$
  • $O(n + k)$ If we generalize the solution to handle any Unicode character. In the worst case $(k = n)$, this becomes $O(n)$.
• Space complexity: $O(1)$ If the we assume the input contains only ASCII characters.
  • $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

---

3. Using Array

Intuition

Since we know the input contains only ASCII characters (128 possible values), we can replace the hash map with a fixed-size array. Array access is faster than hash map lookups, and we avoid the overhead of hashing.

The logic is identical to the hash map approach, but we use the character's ASCII value as the array index.

Algorithm

1. Create an array of size 128 to store character frequencies.
2. Iterate through the string, using each character's ASCII value as an index.
3. Increment the count at each index.
4. Count how many array positions have odd values.
5. Return true if at most one position has an odd count.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        map = [0] * 128
        for ch in s:
            map[ord(ch)] += 1
        count = 0
        for c in map:
            if c % 2:
                count += 1
        return count <= 1

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ If the we assume the input contains only ASCII characters.
  • $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

---

4. Single Pass

Intuition

We can optimize further by tracking the odd count dynamically as we process each character. When a character's frequency becomes even, we decrement the odd count. When it becomes odd, we increment. This way, we know the final answer immediately after one pass without needing a second loop.

Algorithm

1. Create an array of size 128 for character frequencies and initialize an odd counter to 0.
2. For each character in the string:
   • Increment its count in the array.
   • If the new count is even, decrement the odd counter.
   • If the new count is odd, increment the odd counter.
3. Return true if the odd counter is at most 1.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        map = [0] * 128
        count = 0
        for i in range(len(s)):
            map[ord(s[i])] += 1
            if map[ord(s[i])] % 2 == 0:
                count -= 1
            else:
                count += 1
        return count <= 1

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ If the we assume the input contains only ASCII characters.
  • $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

---

5. Using Set

Intuition

A set provides an elegant way to track characters with odd frequencies. When we see a character for the first time, we add it to the set. When we see it again, we remove it. Characters that appear an even number of times cancel out and leave the set. Only characters with odd frequencies remain.

At the end, if the set has at most one element, a palindrome permutation is possible.

Algorithm

1. Initialize an empty set.
2. For each character in the string:
   • If the character is already in the set, remove it.
   • Otherwise, add it to the set.
3. Return true if the set contains at most one character.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        chars = set()
        for c in s:
            if c in chars:
                chars.remove(c)
            else:
                chars.add(c)
        return len(chars) <= 1

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ If the we assume the input contains only ASCII characters.
  • $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique)

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s