How to check if a sequence could be turned into a palindrome

Question

I have to find if a list can be a palindrome. The first part of my program sorts the list.

A = [0, 99, 97, 97, 99, 100, 100, 0]
# sorted:
B = [0, 0, 97, 97, 99, 99, 100, 100]

This list can be a palindrome because it can be reordered to:

[0, 97, 99, 100, 100, 99, 97, 0]

I wrote the following code to return True if the list can be a palindrome.

i=0
counter = 0

while i<len(B):
    if i+1 < len(B):
        if B[i]==B[i+1]:
            print(B[i],B[i+1])
            i+=2
        else:
            i+=1
            counter += 1
    else:
        i+=1

if counter<2:
    return True
return False

However, if I test the list [0, 99, 97, 97, 99, 100, 100, 0, 1], it enters something that looks like a infinite loop. How can I correctly check if a list could be a palindrome?

Answer 1

As we traverse B, we can use a set to keep track of what elements have an odd number so far (using a set here is much faster than a list):

odds = set()
for i in B:
    if i in odds:
        odds.remove(i)
    else:
        odds.add(i)

Then if the length of odds is 0 or 1, print True. Otherwise print False.

print len(odds) <= 1 # prints the value you're looking for

As noted by @Antti, this can be sped up by taking the attribute lookup outside of the loop, if you are optimizing for performance (about 20% speed boost):

odds = set()
remove = odds.remove
add = odds.add
for i in B:
    if i in odds:
        remove(i)
    else:
        add(i)
print len(odds) <= 1