Finding palindromic strings of even length

Question

Given a string of digits. Find the length of longest substring of even length i.e. 0,2,... which is a palindrome or which can be rearranged to form a palindrome ^{(see example below)}.

Here is my code:

def is_palindrome(string):
 length=len(string)
 new_d=[' ']*length
 #For rearranging the substring
 for i in range(length/2):
 new_d[i]=string[i]
 if string[i] in string[i+1:]:
 sindx=length-1-(string[::-1].index(string[i]))
 new_d[-(i+1)]=string[sindx]
 string1=('').join(new_d)
 return string1==string1[::-1]
def substring(number):
 subs=[]
 length=len(number)
 for i in range(length):
 for j in range(i+2,length+1,2):
 #print(number[i:j])
 yield number[i:j]
def count_palindromes(number):
 palindromes=[]
 palindromes.extend(filter(is_palindrome,substring(number)))
 #print(palindromes)
 if len(palindromes):
 lengths=[]
 for i in palindromes:
 lengths.append(len(i))
 lengths.sort(reverse=True)
 return lengths[0]
 else:
 return 0
number=raw_input()
length=count_palindromes(number)
print(length) 

Input: String of numbers(0-9)
Ouput:Length of longest palindromic substring of even length

Example
Input:12345354987
Longest palindromic even length substring: 345354
On rearranging: 345543
Output:6

• aghast: You write "On rearranging". This appears to mean that you want even-length substrings that could be reordered to form a palindrome, rather than actual palindromes themselves. Is this correct?
• katty: @AustinHastings yes that is correct
• katty: @EricDuminil by mistake i'll remove that

Answer 1

Notes

• Your is_palindrome function has a bug. is_palindrome('1101') returns True.

• Be careful with your function names. count_palindromes doesn't count palindromes, it returns the length of the largest one.

• substring returns a generator of substrings. It should be plural.

• If palindromes is a list of palindromes, you can use a list comprehension to get their respective lengths: [len(p) for p in palindromes].

• You don't need to sort a list to find its max: max(palindromes, key=len).

• There's also no need to define an empty list and extending it. You can use list(filter(is_palindrome,substring(number))) or [s for s in substring(number) if is_palindrome(s)].

Theory

If you write a generator which iterates over every even substrings in your string in decreasing length, all you need to check is that every digit appears an even number of time.

Code

from collections import Counter
def all_even_substrings(string):
 n = len(string)
 even_n = n + (n % 2)
 for l in range(even_n, 0, -2):
 for i in range(n + 1 - l):
 yield string[i:i + l]
def could_be_palindrome(substring):
 return all(count % 2 == 0 for count in Counter(substring).values())
def largest_possible_palindrome(string):
 return next((s for s in all_even_substrings(string) if could_be_palindrome(s)), None)
print(largest_possible_palindrome('12345354987'))
# 345354
print(largest_possible_palindrome('12334455987'))
# 334455
print(largest_possible_palindrome('123456789'))
# None

It's concise and pretty straightforward. If no palindrome is possible at all, the function returns None.

Substrings examples

Here's an example for all_even_substrings:

print(list(all_even_substrings('1234')))
# ['1234', '12', '23', '34']
print(list(all_even_substrings('12345')))
# ['1234', '2345', '12', '23', '34', '45']

If you ever need every substring:

def all_substrings(string):
 n = len(string) + 1
 for l in range(n, 0, -1):
 for i in range(n - l):
 yield string[i:i + l]
print(list(all_substrings('123')))
# ['123', '12', '23', '1', '2', '3']
print(list(all_substrings('1234')))
# ['1234', '123', '234', '12', '23', '34', '1', '2', '3', '4']

Answer 2

As I understand your code, you are looking to find substrings that could be arranged to form palindromes. You are looping over various lengths of substrings in your substring function.

Your is_palindrome function, however, spends a great deal of time and effort to formulate the palindrome. This is wasted, because all you really need to know for your scenario is whether each distinct digit appears an even number of times.

If each digit in the substring appears an even number of times, like 112233, then you know you can arrange that substring into a palindrome. If there is a digit that has an odd number of occurrences, then there will be two (since the substrings are even-length, per your problem statement). Which means you have something like 112234 and that cannot be made into a palindrome.

This means you can scan your input string using a "sliding window" and simply update a dictionary of counts as characters are added and removed from the window. What's more, you can stop when you find the first arrangeable substring, and return true. If you start your search from either len(number) or len(number)-1 (if number is odd), then the first result will be the longest result:

start = len(number) if len(number) % 2 == 0 else len(number) - 1
for sublen in range(start, 0, -2):
 if has_substring_that_could_be_a_palindrome(number, sublen):
 print("Longest palindromic substring is", sublen)
 break
else: # for/else, not if/else
 print("No palindromes in", number)