I have the code for this in this GitHub Repo
The Problem
Given a string, determine if a permutation of the string could form a palindrome.
Example 1:
Input: "code"
Output: false
Example 2:
Input: "aab"
Output: true
Example 3:
Input: "carerac"
Output: true
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)
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
Analysis
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 :)
Top comments (0)