Создание палиндромных анаграмм строки длиной до 10^5

Question

Я пробовал следующее, но я пробовал строку из 17 символов.

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 

Это на самом деле мое решение для 'Game of Thrones' challenge on hackerrank. Как уменьшить время выполнения и заставить его работать быстро для строк длиной 10^5?

Спасибо.

Answer 1

Попытка всей комбинации не может быть достаточно быстрой, конечно. Существует гораздо более простой способ сделать это. Он основан на следующем наблюдении: предположим, что count[c] - это число вхождений c в данную строку. Тогда ответ «ДА» тогда и только тогда, когда количество символов с нечетным значением count меньше или равно 1. Это наблюдение дает очень простое решение O(N).

Вот псевдо-код:

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")