Minimum number of letters removed, to make a string Peragram

Question

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 < len(str):
    if(i + 1 < len(str) and str[i] == str[i + 1]):          #If two consecutive chars map, skip matched char
        i += 2
        continue

    toBeRemoved += 1                                        #Increment the number of chars to remove

    if(len(str) % 2 != 0 and isOdd and toBeRemoved > 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?

Answer 1

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

Answer 2

I found a palindrome function 4 times faster than yours.

To write it we start with the simplest case: a zero length string is a palindrome:

def is_palindrome(s):
    if not s:
        return True

A string is a palindrome if the first char equals the last and the rest of the string is a palindrome:

def is_palindrome(s):
    if not s:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

Some timing:

import timeit

def IsPalindrome(s):
    m = int(len(s) / 2)

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

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

    if(str1 != str2):
        return False

    return True

a = timeit.timeit(lambda: IsPalindrome("ivybft7238789r1b23"))

def is_palindrome(s):
    if not s:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])


b = timeit.timeit(lambda: is_palindrome("ivybft7238789r1b23"))
print(a,b)

1.9494715500004531 0.5042732839992823