Palindrome Permutation
Statement
For a given string s, find whether or not a permutation of the string is a palindrome. Return true if such a permutation is possble and false if it isn’t possible.
Constraints
- 1 ≤
s.length()≤ 1000 - The string contains lowercase English characters
Solution
"""
production algorithm
"""
from collections import Counter
class Solution:
def permute_palindrome(self, s):
"""
time complexity O(n)
space complexity O(1)
"""
counter, count = Counter(s), 0
for character in counter:
if counter[character] % 2 == 1:
count += 1
return count < 2"""
unit tests
"""
from unittest import TestCase
from algorithms.counters.palindrome_permutation.solution import Solution
class SolutionTestCase(TestCase):
def test_permute_palindrome_fails(self):
# Given
string = "uvvwwwxxxxyyyyyzzzzzz"
solution = Solution()
# When
actual = solution.permute_palindrome(string)
# Then
expected = False
self.assertEqual(actual, expected)
def test_permute_palindrome_succeeds(self):
# Given
string = "wwxxxxyyyyyyzzzzzzzz"
solution = Solution()
# When
actual = solution.permute_palindrome(string)
# Then
expected = True
self.assertEqual(actual, expected)Strategy
Counters.
Explanation
First, the algorithm counts the frequencies of the characters in the string. Then, it counts the number of odd frequencies. If the total number of odd frequencies is 0 or 1, then there exists some permutation of the characters of the string that’s a palindrome. Otherwise, there’s no permutation of the characters of the string that’s a palindrome.
Time Complexity
First, the algorithm iterates all characters of the string. The time complexity to do so is O(n), where n is the number of characters in the string.
Then, the algorithm iterates all unique characters of the string. Since the characters of the string are lowercase English characters, the time complexity to iterate all unique characters of the string is O(1).
Therefore, the time complexity of the algorithm is O(n).
Space Complexity
At most, the character frequency counter holds 26 unique key-value pairs, since the characters of the string are lowercase English characters. In other words, the auxiliary space taken by the character frequency counter is constant. Therefore, the auxiliary space complexity of the algorithm is O(1).
