# 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 < 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?

• Input 2: abb, Output 2: 0. Surely that's not right. Jul 1, 2014 at 5:25
• @mjolka - abb can be written as bab so that 0 chars to be removed to make it palindrome. I think I didn't described the problem clearly. Jul 1, 2014 at 5:28
• Thanks, the link clarifies it. You're not looking for palindromes, but anagrams of palindromes ("peragrams"). Jul 1, 2014 at 5:32
• @mjolka - Yes. The code works but isn't efficient. Jul 1, 2014 at 5:36

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):
• Good comment. As an additional comment, you don't need to build the list odds as you only care about its length. Also, your final check could be written with max. Here is what I got : print(max(sum(1 for n in Counter(input()).values() if n%2)-1, 0)). Jul 1, 2014 at 8:28
• @Josay - Python not my native. Jul 1, 2014 at 12:10
• Number of lines of the above code have been drastically reduced which is commendable. But I didn't get any performance enhancement, actually my code ran for 0.0630s and yours ran for 0.0690s. Also, the code written in C/C++ by others ran for less than 0.01s (I don't know the exact times). Jul 1, 2014 at 18:42
• @KunalB. What are you planning to do with the extra 20th of a second? Jul 1, 2014 at 18:48
• @KunalB. Your solution becomes slower than the suggested solution when the input becomes bigger. It is easy to see that from a complexity point of view, your solution is at least O(n*log(n)) (because of sorting) while the suggested solution is likely to be 0(n). Jul 2, 2014 at 9:47

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