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

The only thing you have to do is to store the number of times a digit has occcured . Initialize ans=0 and keep on adding count of those digits which has occured even number of times .

and first we have to find longest sub array with non contigious string element in string of even no.then we have to make the palindrome â€¦

This is my code i dont know where it is wrongâ€¦ can u identify it

#include<stdio.h>

#include<string.h>

// A utility function to get max of two integers

int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq

int lps(char *seq, int i, int j)

{

// Base Case 1: If there is only 1 character

if (i == j)

return 1;

// Base Case 2: If there are only 2 characters and both are same

if (seq[i] == seq[j] && i + 1 == j)

return 2;

// If the first and last characters match

if (seq[i] == seq[j])

return lps (seq, i+1, j-1) + 2;

// If the first and last characters do not match

return max( lps(seq, i, j-1), lps(seq, i+1, j) );

}

int main()

{

char seq[] = â€ś12345354987â€ť;//12345

int n = strlen(seq);

printf (â€śThe length is %dâ€ť, lps(seq, 0, n-1));

getchar();

return 0;

}

Can you please elaborate it more?

Just counting the number of even digits is not enough it would result in the rearrangement of sub sequences and sub array .For sub array I believe you need go for sliding window algorithm and manage the state at each window point.

Initial version

Palnidrome.cpp

Corrected Version

Palindrome_edited.cpp

1 Like

@athulpai Unfortunately your solution is giving wrong answer for many of the test cases. See this https://ideone.com/1euDb9

1 Like

Thanks for pointing it out . I made corrections to my code .Initially max_len has to be initialised to the maximum even consecutive element.

Here is the edited version of the code https://ideone.com/P4eMgG

still your approach is wrong.

Check out for this:

1

6568080

Please donâ€™t try to mislead others by posting wrong solution at here.

Below is my answer in Java

```
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class Problem2 {
public static void main(String arg[])
{
String number = "12345354987";//"123225411482222211111";
Map<Character, Integer> map = new HashMap<>();
char[] array = null;
int len = number.length();
boolean palindrom = false;
int maxPalindrom = 0;
for(int j=2; j < len; j +=2)
{
for(int i=0; i <= len - j; i++)
{
array = number.substring(i, i+j).toCharArray();
map.clear();
palindrom = true;
for(char c : array)
{
map.put(c, map.containsKey(c) ? (map.get(c) + 1) : 1);
}
for (Entry<Character, Integer> entry : map.entrySet())
{
if(entry.getValue() % 2 != 0){
palindrom = false;
break;
}
}
if(palindrom)
{
maxPalindrom = array.length;
break;
}
}
}
System.out.print(maxPalindrom);
}
}
```