Generating palindromic anagrams of a string of length upto 10^5

Question

I have tried the following but it takes too much time when I try a string of 17 characters.

string = input()

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]
for p in permute(list(string)):
    mstr = "".join(p)
    if mstr == mstr[::-1]:
        print("YES")
        break

This is actually my solution for 'Game of Thrones' challenge on hackerrank. How can I reduce its execution time and make it run real fast for strings of length 10^5?

Thanks.

Answer 1

Trying all combination cannot be fast enough, of course. There is a much simpler way to do it. It is based on the following observation: let's assume that count[c] is the number of occurrences of c in the given string. Then the answer is YES if and only if the number of characters with odd value of count is less than or equal to 1. This observation gives a very simple O(N) solution.

Here is a pseudo code:

count[c] = 0 for each character c that appears in the string
for i = 1...length(s):
    count[s[i]] += 1
with_odd_count = 0
for each c:
    if count[c] % 2 == 1:
        with_odd_count += 1
if with_odd_count <= 1:
    print("YES")
else:
    print("NO")