DEV Community

loading...

Week 1 Bonus - Palindrome Permutation

ruarfff profile image Ruairí O'Brien ・2 min read

I have the code for this in this GitHub Repo

The Problem

Leetcode Link

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: "aab"
Output: true
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: "carerac"
Output: true
Enter fullscreen mode Exit fullscreen mode

My Tests

import pytest
from .Week1Bonus import Solution

s = Solution()


@pytest.mark.parametrize("test_input", ["code", "abc"])
def test_cannot_permute(test_input):
    assert not s.canPermutePalindrome(test_input)


@pytest.mark.parametrize("test_input", ["aab", "carerac", "a", "aa"])
def test_can_permute(test_input):
    assert s.canPermutePalindrome(test_input)
Enter fullscreen mode Exit fullscreen mode

My Solution

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        if len(s) == 1:
            return True
        char_counts = {}
        for c in s:
            if c in char_counts:
                char_counts[c] = char_counts[c] + 1
            else:
                char_counts[c] = 1
        values = char_counts.values()
        num_odd = 0

        for n in values:
            if n == 1 or n % 2 != 0:
                num_odd += 1

        return num_odd < 2
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

My Commentary

OK, I was pretty lazy with this one but it didn't turn out too terrible.

I thought if you go through the string and figure out how many letters appear an odd number of times, it was then a reasonable solution to check if we had more than one letter appearing an odd number of times. If we do then no permutation of the string can be a palindrome.

I have not put much thought into a better solution yet so if you have any tips please let me know :)

Discussion (0)

pic
Editor guide