5
\$\begingroup\$

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?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Input 2: abb, Output 2: 0. Surely that's not right. \$\endgroup\$ – mjolka Jul 1 '14 at 5:25
  • \$\begingroup\$ @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. \$\endgroup\$ – Kunal B. Jul 1 '14 at 5:28
  • \$\begingroup\$ Thanks, the link clarifies it. You're not looking for palindromes, but anagrams of palindromes ("peragrams"). \$\endgroup\$ – mjolka Jul 1 '14 at 5:32
  • \$\begingroup\$ @mjolka - Yes. The code works but isn't efficient. \$\endgroup\$ – Kunal B. Jul 1 '14 at 5:36
8
\$\begingroup\$

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):
\$\endgroup\$
6
  • 2
    \$\begingroup\$ 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)). \$\endgroup\$ – SylvainD Jul 1 '14 at 8:28
  • \$\begingroup\$ @Josay - Python not my native. \$\endgroup\$ – Kunal B. Jul 1 '14 at 12:10
  • \$\begingroup\$ 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). \$\endgroup\$ – Kunal B. Jul 1 '14 at 18:42
  • 1
    \$\begingroup\$ @KunalB. What are you planning to do with the extra 20th of a second? \$\endgroup\$ – jonrsharpe Jul 1 '14 at 18:48
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – SylvainD Jul 2 '14 at 9:47
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.