#Question 20 solution
from collections import defaultdict, Counter
def longest_palindrome(string):
"""return the length of longest anagram of palindrome in given string - Dynamic programming solution"""
result = defaultdict(int)
string_len = len(string)
palindrome_sorted = []
for i in range(string_len):
result[(i,i+1)] = 1
if string[i:i+1] == string[i+1:i+2]:
result[(i,i+2)] == 1
#In the bruteforce function given below (longest_palindrome_bruteforce) small strings are calculated several times, so
#check from string lengths starting from 3 to string length
#if they are palindrome, or j is shifting window,
#k is starting index and l is last index
for j in range(3,string_len+1):
for k in range(string_len-j):
l = k+j
if string[k] == string[l] and result[(k+1,l-1)]:
result[(k,l)] = 1
palindrome_sorted = sorted(result.keys(), key=lambda x:x[1]-x[0],reverse=True)
if not palindrome_sorted:
return 0
final = palindrome_sorted[0]
return final[1] - final[0] + 1
def longest_palindrome_bruteforce(string):
string_length = len(string)
longest_current = (0,None,None)
longest_current_string = ""
for i in range(string_length):
for k in range(i,string_length+1):
if is_palindrome(string[i:k]):
if k-i > longest_current[0]:
longest_current = (k-i,i,k)
longest_current_string = string[i:k]
return longest_current
from itertools import chain, combinations
def get_partitions(string):
#convert numbers from 0 to 2^^len(string) into binary, for each number,
#categorize 0 indices and 1 indices into two subsets
string_length = len(string)
joy_max = 0
pot = long(2**string_length)
i = long(0)
while(i < pot):
x = bin(i).split('b')[-1]
pattern = '0' * (string_length - len(x)) + x
pattern_array = list(pattern)
first_array = []
second_array = []
for x,y in enumerate(pattern_array):
if int(y):
first_array.append(string[x])
else:
second_array.append(string[x])
a = longest_palindrome(first_array)
b = longest_palindrome(second_array)
if a*b > joy_max:
joy_max = a*b
i = i+1
return joy_max
print get_partitions("abccbaabccbaxyyx")
#another question where a string is anagram of palindrome. In the solution, i have coded the following logic as being a potential, but this is sufficient condition to check if it is a anagram.
def is_palindrome_anagram(string):
a = Counter(string)
b = [ (i%2==0) for i in a.values()]
#potential palindrome anagram will have at max one char that occurs odd number
if b.count(False) >1 :
return False
else:
return True
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.