## Groupon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

The fact that we are only looking for even length palindrome makes it a lot easier.

For even length palindrome, the middle 2 characters are the same, so we can find all occasion and find the longest palindrome from there.
Record the max length and the start of of longest palindrome, and output using these data at the end.

``````char* leftmostOfPalindrome(char* r)
{
char* l = r++;
while(*(l-1) == *(r+1)){l--; r++;}
return l;
}
char* longestPalindrome( char* s)
{
char* cur = s, *cur_lt, *result, *palin;
int l = 0, max_l = 0;
while(*cur != '\0')
{
if(*cur == *(cur+1))
{
cur_lt = leftmostOfPalindrome(cur);
l = (cur - cur_lt + 1) * 2;
if(l > max_l){max_l = l; result = cur_lt;}
}
cur++;
}
palin = (char*) malloc (max_l+1);
for(l = 0; l < max_l; l++) palin[l] = result[l];
palin[l] = '\0'; //if max_l = 0, palin = "\0";
return palin;
}``````

Code Tested for C++ using "testtsettesttset12312313", "1331", "11111111111111"

Worst case scenrio, "11111111111111", etc. It will have O(n^2). Barely any extra memory is allocated (you can't not use the malloc since you need to return it while not destroying the original data,

Comment hidden because of low score. Click to expand.
0
of 0 vote

Manache's algorithm is the best for it after certain modification. You can read it on leetcode.com Its an O(n) time algorithm.

However, a method that strikes easily is DP.It take O(n2) time and space.

let l[i][j] denote the length of palindrome from ith index to jth index.
using dynamic programming, we can easily solve this.
if x1[i]==x1[i+1], then l[i][i+1]=1
for j<=i, l[i][j]=0 since we are looking for even length palindrome.
otherwise, if x1[i]==x1[j] then l[i][j]=l[i+1][j-1]+2 if the inner substring i.e. x1[i+1][j-1] is a palindrome i.e. l[i][j]!=l[i+1][j-1]
if x1[i]!=x1[j] then l[i][j]=l[i+1][j-1]

int calculatePalindrome(){
int max=0;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
if(j<=i)
l[i][j]=0;
for(int i=0;i<16;i++)
if(x1[i]==x1[i+1]){
l[i][i+1]=2;
max=2;
}
for(int j=1;j<16;j++)
for(int i=0;i<j;i++){
if(x1[i]==x1[j]&&l[i][j]!=l[i+1][j-1]){

l[i][j]=l[i+1][j-1]+2;
if(max<l[i][j]){
max=l[i][j];
cout<<"ij"<<i<<j<<endl; }
}
else l[i][j]=l[i+1][j-1];
}
return max;
}

Comment hidden because of low score. Click to expand.
0

@alex: Nice algo but I think there is a typo.I think you meant in your comments
if x1[i]==x1[i+1], then l[i][i+1]=1 should be
if x1[i]==x1[i+1], then l[i][i+1]=2
no?

Comment hidden because of low score. Click to expand.
0

@alex it doesn't work.

``````#include <stdio.h>

#define SIZE(x1) sizeof x1/sizeof x1[0]
int l[100][100] = {0};

int calculatePalindrome(){
int max=0, i, j;
for(i=0;i<SIZE(x1);i++)
for(j=0;j<SIZE(x1);j++)
if(j<=i)
l[i][j]=0;
for(i=0;i<SIZE(x1);i++)
if(x1[i]==x1[i+1]){
l[i][i+1]=2;
max=2;
}
for(j=1;j<SIZE(x1);j++)
for(i=0;i<j;i++){
if(x1[i]==x1[j]&&l[i][j]!=l[i+1][j-1]){
l[i][j]=l[i+1][j-1]+2;
if(max<l[i][j]){
max=l[i][j];
}
}
else l[i][j]=l[i+1][j-1];
}
return max;
}

int main(void) {
printf("%d", calculatePalindrome());
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@alex

Below is the algorithm given by my friend.

Complexity: Time - O(n2), Space - O(1)

1) Have counters i and j point to first and second elements and mark them left and right of current largest palindrome.
2) Decrement left and increment right until left>0 and right<length of array and array[left]=array[right]
3) Store the longest palindrome and its count
4) Repeat the process by incrementing i and j till i points to length-1 and j points to length

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check this out:

``````bool IsPalindrome(char str[], int startIndex, int endIndex)
{
while (startIndex < endIndex)
{
if (str[startIndex] != str[endIndex])
{
return false;
}
++startIndex;
--endIndex;
}
return true;
}

int LargestEvenPalin(char str[], int* startIndex)
{
int len = strlen(str);
bool bEven = (len % 2 == 0);
int j = 0;
int lenResult = 0;
for(int i = 0; i < len - 1; ++i)
{
j = len - (bEven ? 1 : 2);
if (j - i > lenResult)
{
for(; i < j; j -= 2)
{
if (j - i > lenResult)
{
if (IsPalindrome(str, i, j))
{
if ((j - i) > lenResult)
{
*startIndex = i;
lenResult = j - i;
}
}
}
else
{
break;
}
}
}
else
{
break;
}
bEven = !bEven;
}

return lenResult + 1;
}

void RunDriver()
{
//input
char str[1000];
int startIndex = -1;
cin.getline(str, 1000);

int resLen = LargestEvenPalin(str, &startIndex);
if (resLen > 1)
{
char* resultString = str + startIndex;
resultString[resLen] = '\0';
cout << endl << "Longest possible even palindrome is: " << resultString << endl;
}
else
{
cout << endl << "No Longest possible even palindrome exists." << endl;
}
}``````

0(n^2) if no palindrome exists... :)

Comment hidden because of low score. Click to expand.
0

I tried to shorten LargestEvenPalin()...

``````int LargestEvenPalin(char str[], int* startIndex)
{
int len = strlen(str);
bool bEven = (len % 2 == 0);
int lenResult = 0;
int j = len - (bEven ? 1 : 2);
for(int i = 0; (j - i > lenResult); ++i)
{
for(; (j - i > lenResult); j -= 2)
{
if (IsPalindrome(str, i, j))
{
*startIndex = i;
lenResult = j - i;
}
}
bEven = !bEven;
j = len - (bEven ? 1 : 2);
}

return lenResult + 1;
}``````

Let me know if there is any issue in this code... :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.test;

import java.io.IOException;

public class StringPallindrome {

/**
* @param args
* @throws IOException
*/
static int maxindex=-1,maxcount=0;
public static void main(String[] args) throws IOException {
String s = "aba";
findLargestOddPallindrome(s);
findLargestEvenPallindrome(s);
System.out.println("Largest Palindrome:::"+s.substring(maxindex,maxindex+maxcount));

}

private static void findLargestOddPallindrome(String s) {
int j = 0,l, count, index = -1;
char[] a = s.toCharArray();
for (int i = 0; i < a.length - 1; i++) {
l=i;
j = i;
count=1;
while (l > 0 && j < a.length-1) {
if (a[--l] == a[++j]) {
count+=2;
index = l;
} else {
break;
}
}
if (count > maxcount) {
maxcount = count;
maxindex=index;
}
}

}

private static void findLargestEvenPallindrome(String s) {
int j = 0,l, count, index = -1;
char[] a = s.toCharArray();
for (int i = 0; i < a.length - 1; i++) {
l=i;
j = i+1;
count=2;
while (l > 0 && j < a.length-1 && a[l]==a[j]) {
if (a[--l] == a[++j]) {
count+=2;
index = l;
} else {
break;
}
}
if (count > maxcount) {
maxcount = count;
maxindex=index;
}
}

}

}``````

Comment hidden because of low score. Click to expand.
0

Brute force way.. no use of past result why do you have to proceed to the right if you already have a max pallindrome which is greater than the twice of the number of elements to the right of the center vertex.
n square times if the whole string is pallindrome and other optimization possible.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a stack, and set a flag to record whether this time pop some elements.
flag == 0 means there is no element being poped in prior loop,
flag == 1 means there is one element being poped in prior loog.
1. Input an element, when the stack is empty
1)if the element is equal to the stack[top]
2)if the element is not equal to the stack[top]
2. Input an element, when the stack is not empty

You can find the detail logic in the following code segments.
The time complexity is O(n).

``````int getLongestEvenPalindrome(char source[], int& end)
{
int i = 0, top = -1;
int max = -1, pop = 0;
int tmp = 0, tend = 0;
int len = strlen(source);
char stack[MAX];

for(i = 0; i < len; i++)
{
if(top > -1)
{
if(source[i] == stack[top])
{
if(pop == 0)
{
pop = 1;
tmp = 2;
tend = i;
}
else if(pop == 1)
{
tmp += 2;
tend = i;
}
top--;
}
else if(source[i] != stack[top])
{
if(pop == 1)
{
top = -1;
pop = 0;
stack[++top] = source[i];

if(tmp > max)
{
max = tmp;
end = tend;
}
tmp = 0;
}
else if(pop == 0)
{
stack[++top] = source[i];
}
}
}
else if(top == -1)
{
stack[++top] = source[i];
}
}
if(tmp > max)
{
max = tmp;
end = tend;
}

return max;
}

int main()
{
int end = 0;
char source[MAX] = "abcicbbcdefggfed";
int max = getLongestEvenPalindrome(source, end);

cout << max << endl;
for(int i = max - 1; i >= 0; i--)
{
cout << source[end - i];
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The below code is simple and has only O(n) time complexity.

``````def calculate_longest_palindrome(s, start, end, palindrome):
new_palindrome = s[start : end]
if not palindrome or len(new_palindrome) > len(palindrome):
return new_palindrome
return palindrome

def get_longest_even_palindrome(s):
position      = -1
in_palindrome = False
palindrome    = None
for i in range(0, len(s)):
if position == -1:
position = i
continue

if s[i] == s[position]:
position      -= 1
in_palindrome  = True
else:
if in_palindrome:
palindrome    = calculate_longest_palindrome(s, position + 1, i, palindrome)
in_palindrome = False
position = i

# Final check...
if in_palindrome:
palindrome = calculate_longest_palindrome(s, position + 1, len(s), palindrome)

return palindrome

print get_longest_even_palindrome('abcicbbcdefggfed')``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n)? Are you sure? I am not used to this language that you use so I am having a very hard time to read, but I don't think this gives O(n).

What is the time complexity for "11111111...11111" ? It looks like O(n^2) to me.
In fact, I can't understand what it does for "111111111111111".

Comment hidden because of low score. Click to expand.
0
of 0 vote

if the length of the string is even,then the problem can be solved easily.
if the length of the string is odd,
eg.
cdefggfed

tansform to a another string #c#d#e#f#g#g#f#e#d#

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class SubString {
public static String s = "abcicbbcdefggfed ";
public static String out1;
public static int max=0;
public static void main(String args[]) {
int l = s.length();
for (int i = 0; i < l; i++) {
for (int j = 1; j <= l - i; j++) {
StringBuffer br = new StringBuffer();
br.append(s.substring(i, j + i));
if (s.substring(i, i + j).equals(br.reverse().toString())
&& s.substring(i, i + j).length() % 2 == 0) {
}

}
}
if(l1.size()>0){
for(int k=0;k<l1.size()-1;k++){
if(l1.get(k).length()<l1.get(k+1).length()){ max=k+1;}
}
System.out.println(l1.get(max)); }
else {
System.out.println("i am sorry i cannot find even palindrome in given string tryother");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

let the number of even palindromes = j and k be the length of the longest even palindrome.
The below code takes O(n) + O(jk)
and a space complexity of O(j) + O(j)

``````//Find the longest even palindrome in a string

#include<iostream>
using namespace std;

int main() {
char string[50];
int n,j,k;
int arr[50], arrlen[50];
cin>>string;
for (n=0; string[n]!='\0'; n++);
j=0;
for (int i=0; i<n; i++) {
if (string[i] == string[i+1]) {
arr[j]=i;
j++;
}
}
if (j>0) {
for (int i=0; i<j; i++) {
k=1;
while (string[arr[i]-k] == string[arr[i]+1+k])
k++;
arrlen[i] = k;
}
int maxLength = arrlen[0];
k=0;
for (int i=1; i<j; i++) {
if (arrlen[i]>maxLength) {
maxLength = arrlen[i];
k = i;
}
}
for (int i= (arr[k] - maxLength + 1); i < (arr[k] + 1 + maxLength); i++)
cout<<string[i];
}
cout<<endl<<endl;
system("pause");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't we start finding from the middle and widen the string if pallindrome else shift the center element or vertex. We are interested in max Pallindrom so we can always decide if we really need to look further for a pallindrome or not if we use this approach.

Comment hidden because of low score. Click to expand.
0

Will this approach handle multiple palindromes in a given string?

Comment hidden because of low score. Click to expand.
0
of 0 vote

A more readable solution that makes use of recursion. Hope it helps somebody out there

``````package algorithm.palyndrom;

public class LengthLongestPalyndrom {

public int longestPalyndrom(char[] string) {
return longestPalyndromLoop(string, 0);
}

private int longestPalyndromLoop(char[] string, int begin) {
int nextCentre = findNextCentre(string, begin);
if (nextCentre != -1) {
return Math.max(calculatePalyndromLenght(string, nextCentre), longestPalyndromLoop(string, nextCentre + 1));
}
return 0;
}

private int findNextCentre(char[] string, int begin) {
for (int i = begin; i < string.length - 1; i++) {
if (string[i] == string[i + 1]) {
return i;
}
}
return -1;
}

private int calculatePalyndromLenght(char[] string, int centre) {
int palindromeLength = 2;

int leftIndex = centre - 1;
int rightIndex = centre + 2;

while (leftIndex >= 0 && rightIndex < string.length) {
if (string[leftIndex] == string[rightIndex]) {
palindromeLength += 2;
leftIndex--;
rightIndex++;
} else {
break;
}
}
return palindromeLength;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the task is to find longest palindrome from a given set of characters, that is the string input. The logic which I think is to be used is, that an even palindrome can be formed by even number of characters, like abba, or aabbaa . So my logic would be to first count the number of characters and their occurrence in the string and then find the characters with even number of occurrences. The length of the max string is sum of all even occurrences of Characters.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the occurrence of repeating characters and expand from there. Keep track of the longest seen palindrome.

``````public static String longestEvenPalindrome(String s){
if(s.length() == 0 || s.length() == 1){
return "";
}

String longestSoFar = "";
for(int i=1;i<s.length();i++){
if(s.charAt(i) == s.charAt(i-1)){
String temp = expand(s, i-1, i);
if(temp.length() > longestSoFar.length()){
longestSoFar = temp;
}
}
}

return longestSoFar;
}

private static String expand(String s, int i, int i2) {
StringBuilder sb = new StringBuilder();
while(i>=0 && i2<s.length()){
if(s.charAt(i) == s.charAt(i2)){
sb.insert(0, s.charAt(i));
sb.append(s.charAt(i));
i--; i2++;
}else{
break;
}
}
return sb.toString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution. I have checked it. It works. Please do find the code below its written in c.

``````#include<stdio.h>
#include<string.h>

int main()
{
char c[] = "abcicbbcdefggfed",*ptr = c,*c1,*c2,*prev,*str;
int count,maxcount = 0;
while(*ptr != '\0') {
count = 0;
if(*ptr == *(ptr+1)) {
count = 2;
c1 = ptr - 1;
c2 = ptr + 2;
while(*c1 == *c2) {
count = count +2;
prev = c1;
c1--;
c2++;
}
if(count > maxcount) {
maxcount = count;
str = prev;
}
}
ptr++;
}
printf("\n");/*lets print the biggest even palindrome*/
while(maxcount != 0) {
printf("%c",*str);
str++;
maxcount--;
}
printf("\n");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String largestEvenPalindrome()
{
int low=0,high=0,count=0;
//values for the highest length palindrome
int pLow=0,pHigh=0,pHighestCount=0;
for(int i=0;i<s.length()-1;i++)
{
//low and high correspond to the adjacent cells
low=i;
high=i+1;
count=0;
while((low>=0)&&(high<=s.length()-1))
{
if(s.charAt(low)!=s.charAt(high))
break;
else
{
//if 2 adjacent cells have the same character, we move low and high 			//away from each other each time as long as there is a match
low--;
high++;
count+=2;
}
if(count>pHighestCount)
{
pHighestCount=count;
pLow=low+1;
pHigh=high-1;
}
}
}
if(pHigh!=0)
return s.substring(pLow, pHigh+1);
else
return null;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This will take O(n) time.

``````#include<iostream>
#include<string.h>
using namespace std;

string update_input(string s)
{
int length=s.length();
if(length==0)
return "^\$";
string ret="^";
for(int i=0;i<length;i++)
{
ret=ret+"#"+s.substr(i,1);
}
ret=ret+"#\$";
return ret;
}

string process_input(string s)
{
string T=update_input(s);
int n=T.length();
int *p=new int[n];
int C=0,R=0;
for(int i=1;i<n-1;i++)
{
int i_mirror=2*C-i;

p[i]=(R>i)?min(R-i,p[i_mirror]):0;

while(T[i+1+p[i]]==T[i-1-p[i]])
p[i]++;

if(i+p[i]>R)
{
C=i;
R=i+p[i];
}

}
int maxLen=0;
int centerIndex=0;
for(int i=1;i<n-1;i++)
{
if(p[i]>maxLen)
{
if(p[i]%2==0)//this if is only for printing even length palindrom
{
maxLen=p[i];
centerIndex=i;
}
}
}
delete[] p;

return s.substr((centerIndex - 1 - maxLen)/2, maxLen);

}

int main()
{
string input="zabbacabc";
string z=process_input(input);
cout<<z<<"\n";
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {
System.out.println("The longest even palidrome is "
+ findLongestPalindrome("testtsettesttset12312313"));
}

private static String findLongestPalindrome(String string) {
String palindrome = null;
int counter = 0;

int index = 0, maxCounter = -1;

while (index >= 0) {
counter = 0;
string = string.substring(index);
index = findDoubleLetter(string);
counter = +2;
if (index != -1) {
int start = index - 2;
int end = index + 1;
while (start > 0 && end < string.length() - 1) {
if (string.charAt(start) == string.charAt(end)) {
counter += 2;
end++;
start--;
} else {
break;
}
}
if (counter > maxCounter) {
palindrome = string.substring(start, end + 1);
maxCounter = counter;
}

}
if (index != -1) {
index++;
}
}

return palindrome;
}

private static int findDoubleLetter(String string) {
for (int i = 0; i < string.length() - 1; i++) {
if (string.charAt(i) == string.charAt(i + 1)) {
return (i + 1);

}
}
return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

can anyone provide a simple algo for this, i don't want the code but just a blueprint.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findLongestPalindromeOfEvenLength() {
int i = 0, j = 0, l = 0;
int palStrLen = getPalIp().length();
int newPalLen = 0, oldPalLen = 0;
System.out.println("Length of the original string is " + palStrLen);
l = palStrLen - 1;
for(int k = 0;k<palStrLen;k++)
{
for (i = 0, j = l; i < j;) {
if(isPalindrome(getPalIp(), i, j))
{
newPalLen = (j+1) - i;
break;
}
else
{
i++;
j = l;
}
}
if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
oldPalLen = newPalLen;
l--;
}

System.out.println("length of longest palindrome is "+oldPalLen);
return 0;
}

public Boolean isPalindrome(String s, int i, int j)
{
while(i<=j)
{
if(s.charAt(i) == s.charAt(j))
{
i++; j--;
}
else return false;
}
return true;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findLongestPalindromeOfEvenLength() {
int i = 0, j = 0, l = 0;
int palStrLen = getPalIp().length();
int newPalLen = 0, oldPalLen = 0;
System.out.println("Length of the original string is " + palStrLen);
l = palStrLen - 1;
for(int k = 0;k<palStrLen;k++)
{
for (i = 0, j = l; i < j;) {
if(isPalindrome(getPalIp(), i, j))
{
newPalLen = (j+1) - i;
break;
}
else
{
i++;
j = l;
}
}
if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
oldPalLen = newPalLen;
l--;
}

System.out.println("length of longest palindrome is "+oldPalLen);
return 0;
}

public Boolean isPalindrome(String s, int i, int j)
{
while(i<=j)
{
if(s.charAt(i) == s.charAt(j))
{
i++; j--;
}
else return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findLongestPalindromeOfEvenLength() {
int i = 0, j = 0, l = 0;
int palStrLen = getPalIp().length();
int newPalLen = 0, oldPalLen = 0;
System.out.println("Length of the original string is " + palStrLen);
l = palStrLen - 1;
for(int k = 0;k<palStrLen;k++)
{
for (i = 0, j = l; i < j;) {
if(isPalindrome(getPalIp(), i, j))
{
newPalLen = (j+1) - i;
break;
}
else
{
i++;
j = l;
}
}
if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
oldPalLen = newPalLen;
l--;
}

System.out.println("length of longest palindrome is "+oldPalLen);
return 0;
}

public Boolean isPalindrome(String s, int i, int j)
{
while(i<=j)
{
if(s.charAt(i) == s.charAt(j))
{
i++; j--;
}
else return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findLongestPalindromeOfEvenLength() {
int i = 0, j = 0, l = 0;
int palStrLen = getPalIp().length();
int newPalLen = 0, oldPalLen = 0;
System.out.println("Length of the original string is " + palStrLen);
l = palStrLen - 1;
for(int k = 0;k<palStrLen;k++)
{
for (i = 0, j = l; i < j;) {
if(isPalindrome(getPalIp(), i, j))
{
newPalLen = (j+1) - i;
break;
}
else
{
i++;
j = l;
}
}
if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
oldPalLen = newPalLen;
l--;
}

System.out.println("length of longest palindrome is "+oldPalLen);
return 0;
}

public Boolean isPalindrome(String s, int i, int j)
{
while(i<=j)
{
if(s.charAt(i) == s.charAt(j))
{
i++; j--;
}
else return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findLongestPalindromeOfEvenLength() {
int i = 0, j = 0, l = 0;
int palStrLen = getPalIp().length();
int newPalLen = 0, oldPalLen = 0;
System.out.println("Length of the original string is " + palStrLen);
l = palStrLen - 1;
for(int k = 0;k<palStrLen;k++)
{
for (i = 0, j = l; i < j;) {
if(isPalindrome(getPalIp(), i, j))
{
newPalLen = (j+1) - i;
break;
}
else
{
i++;
j = l;
}
}
if((newPalLen > oldPalLen) && (newPalLen % 2 == 0)) //Omit %2 if the question is not for longest even palindrome
oldPalLen = newPalLen;
l--;
}

System.out.println("length of longest palindrome is "+oldPalLen);
return 0;
}

public Boolean isPalindrome(String s, int i, int j)
{
while(i<=j)
{
if(s.charAt(i) == s.charAt(j))
{
i++; j--;
}
else return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about just sorting the input string and then walk up the sorted string extracting pairs of chars and adding them to the beginning and end of a string, so build it from the inside out. If the problem were relaxed to allow odd, then first scan the sorted string for odd numbered set and use that as the middle of the result.

Comment hidden because of low score. Click to expand.
0

@dn

This algorithm will not work. The problem is to find existing palindromes from the input string. Not form palindromes from available characters?

Input: abab
should return null, but your code will return abba

Comment hidden because of low score. Click to expand.
0

ah,ok. Sorry misunderstood that then.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.