Palindrome Permutation Python Solution

Tested Python solution for LeetCode 266 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 266, Easy. Topics: Bit Manipulation, Hash Table, String. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 266   # by problem number
lcpy gen -s palindrome_permutation   # by problem name

​

Problem

Given a string s, return true if a permutation of the string could form a palindrome and false otherwise.

​

Examples

Input: s = "code"
Output: false

Input: s = "aab"
Output: true

Input: s = "carerac"
Output: true

​

Constraints

• 1 <= s.length <= 5000
• s consists of only lowercase English letters.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import Counter


class Solution:
    # Time: O(n)
    # Space: O(1) for the 26-letter alphabet
    def can_permute_palindrome(self, s: str) -> bool:
        counts = Counter(s)
        return sum(count % 2 for count in counts.values()) < 2

​

Complexity

Time	Space
O(n)	O(1) for the 26-letter alphabet

​

Tags

NeetCode All.