Groupon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
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;
}
@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?
@alex it doesn't work.
#include <stdio.h>
#define SIZE(x1) sizeof x1/sizeof x1[0]
char x1[] = {"abedeedkbadddddo"};
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;
}
@alex
Can you please explain your algorithm?
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
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... :)
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... :)
package com.test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class StringPallindrome {
/**
* @param args
* @throws IOException
*/
static int maxindex=-1,maxcount=0;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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;
}
}
}
}
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.
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;
}
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')
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();
LinkedList<String> l1 = new LinkedList();
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) {
l1.add(s.substring(i,i+j));
}
}
}
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");
}
}
}
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;
}
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.
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;
}
}
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.
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();
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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.
@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
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.
Code Tested for C++ using "testtsettesttset12312313", "1331", "11111111111111"
- Mo Lam May 15, 2013Worst 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,