Minimum number of letters removed, to make a string Peragram

Here is the link to the problem Peragrams.


Peragrams: If a word is an anagram of at least one palindrome, we call it a Peragram.


Problem: Given a string, find the minimum number of letters you have to remove from it, so that the string becomes a Peragram.



Input #1: abc


Output #1: 2


Input #2: abb


Output #2: 0


My Python code is as follows:

# Checks whether a string is palindrome
def IsPalindrome(str):
    m = int(len(str) / 2)

    str1 = str[:m]
    str2 = str[m:][::-1]

    if(len(str) % 2 != 0):
        str2 = str[m + 1:][::-1]

    if(str1 != str2):
        return False

    return True

##################################################

str = input()               #Read input from console
toBeRemoved = 0

if(IsPalindrome(str)):      #If the string is already a palindrome
    print(0)
    exit(0)

str = ''.join(sorted(str))  #Sort the string

i = 0
isOdd = True

while i  0):   #If the string is odd length, skip first non-duplicate character & skip to next char
        isOdd = False
        toBeRemoved -= 1
        i += 1
        continue

    str = str[:i] + str[i + 1:] #Remove the char at i

    if(IsPalindrome(str)):
        break

print(toBeRemoved)

How can I improve the code to get a better running time?

The approach you are taking is to remove letters until at most one of them has an odd count. Once you realise that, the solution becomes obvious:

from collections import Counter

s = input() # don't call your own variable 'str'

c = Counter(s)

odds = [None for n in c.values() if n % 2]

if odds:
    print(len(odds) - 1)
else:
    print(0)

collections.Counter is a dict subclass to make counting the letters simpler. You don't actually need to create the substrings or check whether they are peragrams.

You should read and consider following the style guide, PEP-0008. For example:

if(IsPalindrome(str)):

should be:

if is_palindrome(s):

StackExchange Code Review Q#55761, answer score: 8