# Can Form Palindrome from String

### Example base code from Geeks for Geeks¶

In :
# 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 =  * (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 :
def can_make_palindrome(string):
letters = set()
for c in string:
if c in letters:
letters.remove(c)
else:
length = len(string)
return (not (letters_length := len(letters)) and (length & 1)) or (
length and letters_length == 1
)

In :
GEEKSFORGEEKS, GEEKSOGEEKS = "geeksforgeeks", "geeksogeeks"

In :
for string, expected in ((GEEKSFORGEEKS, False), (GEEKSOGEEKS, True)):
assert can_make_palindrome(string) is expected

In :
%%timeit
canFormPalindrome(GEEKSOGEEKS)

104 µs ± 1.98 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


### O(n) time¶

In :
%%timeit
can_make_palindrome(GEEKSOGEEKS)

5.52 µs ± 106 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In :
%%timeit
canFormPalindrome(GEEKSFORGEEKS)

53.9 µs ± 2.16 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


### O(n) time¶

In :
%%timeit
can_make_palindrome(GEEKSFORGEEKS)

5.9 µs ± 80.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)