Coding question on Palindrome


#1

Raja loves Strings. In Strings he specially loves palindromes.Palindromes are strings that read the same when read forward or backwards. Here Palindromes considered are only of even length(maybe 0). His Teacher gave me him a long string consisting of only digits as a gift on his birthday. Now Raja wants to know The longest subarray whose elements (i.e digits) can be rearranged to form a palindrome of even length. Raja is unable to figure out the solution to the problem so he asks for your help.

INPUT SPECIFICATION - The function contains one argument - A String S consisting of digits (0-9). First and only line of input consists of S (1 <= |S| <= 100000). OUTPUT SPECIFICATION - You must return a single integer denoting the longest subarray whose elements (digits) can be rearranged to form a palindrome of even length.If no such subarray can be found return 0. Example - Sample Test Case 1

Input

12345354987

Output

6 Explanation : No subarray can be rearranged to form even length of palindrome .Hence 0.

Explanation : Here the longest subarray is 345354 which can be rearranged to form 345543 which is a palindrome of even length 6.Hence and is 6.

Sample Test Case 2-

Input

12345

Output

0


#2

Create a counter array
Fill it with count of digit in array
Array will have only 10 elements
Now if count of a digit is odd, we can take only even times appearance for palindrome.


#3

This can be solved using programming technique called Dynamic Programming.
Here, we will take a three dimensional array for memoization. dp [n] [n] [10]
where n is the length of the string.

dp [i] [j] [d] stores the no. of digit (d+1) in string from position i to position j.

After populating the dp array, start looking from highest difference in i & j to lowest difference, to check that each digit is present in even number i.e. 0,1,2,3.
Even if one digit is present in odd number we will eliminate that. The highest difference in i & j where our conditions are met, is our length of the palindrome.

P.S. - Try to understand this dp, cos its a bit complicated. If u get it, its great otherwise do reply with your doubt.