Can Form Palindrome from String

Example base code from Geeks for Geeks

In [48]:
# Python3 implementation to check if
# characters of a given string can
# be rearranged to form a palindrome

NO_OF_CHARS = 256

# function to check whether characters
# of a string can form a palindrome
def canFormPalindrome(st):

    # Create a count array and initialize
    # all values as 0
    count = [0] * (NO_OF_CHARS)

    # For each character in input strings,
    # increment count in the corresponding
    # count array
    for i in range(0, len(st)):
        count[ord(st[i])] = count[ord(st[i])] + 1

    # Count odd occurring characters
    odd = 0

    for i in range(0, NO_OF_CHARS):
        if count[i] & 1:
            odd = odd + 1

        if odd > 1:
            return False

    # Return true if odd count is 0 or 1,
    return True


# Driver program
if canFormPalindrome("geeksforgeeks"):
    print("Yes")
else:
    print("No")

if canFormPalindrome("geeksogeeks"):
    print("Yes")
else:
    print("No")

# This code is contributed by Nikita Tiwari.
No
Yes

Another approach.

We can do it in O(n) time using a set.

Following are detailed steps.

  1. Create a character set.
  2. Traverse the given string.
  3. For every character in the string, remove the character if the set already contains else add to the set.
  4. If the string length is even the set is expected to be empty.
  5. Or if the string length is odd the set size is expected to be 1
  6. On the above two conditions (3) or (4) return true else return false.
In [56]:
def can_make_palindrome(string):
    letters = set()
    for c in string:
        if c in letters:
            letters.remove(c)
        else:
            letters.add(c)
    length = len(string)
    return (not (letters_length := len(letters)) and (length & 1)) or (
        length and letters_length == 1
    )
In [57]:
GEEKSFORGEEKS, GEEKSOGEEKS = "geeksforgeeks", "geeksogeeks"
In [58]:
for string, expected in ((GEEKSFORGEEKS, False), (GEEKSOGEEKS, True)):
    assert can_make_palindrome(string) is expected
In [52]:
%%timeit
canFormPalindrome(GEEKSOGEEKS)
104 µs ± 1.98 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

O(n) time

In [53]:
%%timeit
can_make_palindrome(GEEKSOGEEKS)
5.52 µs ± 106 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [54]:
%%timeit
canFormPalindrome(GEEKSFORGEEKS)
53.9 µs ± 2.16 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

O(n) time

In [55]:
%%timeit
can_make_palindrome(GEEKSFORGEEKS)
5.9 µs ± 80.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)