Q20: max joy

#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): string_length = len(string) joy_max = 0 pot = long(string_length) i = long(0) while(i < pot): first_array = string[:i] second_array = string[i+1:] 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.