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?

• mjolka: Input 2: abb, Output 2: 0. Surely that's not right.
• Kunal B.: @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.
• mjolka: Thanks, the link clarifies it. You're not looking for palindromes, but anagrams of palindromes ("peragrams").
• Kunal B.: @mjolka - Yes. The code works but isn't efficient.

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

• SylvainD: 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)).
• Kunal B.: @Josay - Python not my native.
• Kunal B.: 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).
• jonrsharpe: @KunalB. What are you planning to do with the extra 20th of a second?
• SylvainD: @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).

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