Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
DP solution. I would commit code, but write a formula.
if(s[i] == s[j])
T[i,j] = T[i + 1,j - 1] + 1
else
T[i,j] = max(T[i + 1,j],T[i,j - 1])
result T[0,n] then we need to find position of i and j where result occurs.
/**O(n^2)**/
public class LargestPalindromicSubstring {
private static final int ODD = 1;
private static final int EVEN = 2;
public static int max = 0;
public static int left=0, right=0;
/**
* @param args
*/
public static void main(String[] args) {
max = left = right = 1;
for(int i=0; i<args[0].length(); i++){
GetLongestPalindrome(i, args[0], ODD); //Check for odd length palindrome about i.
GetLongestPalindrome(i, args[0], EVEN); //Check for even length palindrome about i.
}
String largest = "";
for(int i=left;i<=right;i++){
largest += args[0].charAt(i);
}
System.out.println("The string -"+args[0]+"- has maximum length palindromic substring of length "+ max +".\n\nThe substring "
+ "is "+largest);
}
public static void GetLongestPalindrome(int pos, String arg, int len){
int i=pos, j=pos;
if(len==EVEN) j++;
len = 0;
while(i>=0 && j< arg.length()){
if(arg.charAt(i) == arg.charAt(j)){
len = j-i+1;
} else break;
i--;j++;
}
if(len > max){
max = len; left = i+1; right = j-1;
}
return;
}
}
if (T[i][ i + T[0][n-1] - 1 ] == T[0][n-1])
{
// This should answer your question
pallindrome = s.substr(i, T[0][n-1]);
}
int T[ MAX ][ MAX ], n, i, j, k;
string s;
cin >> s;
n = s.length();
for (T[0][0] = 1, i = 1; i < n; ++i)
{
T[i][i] = 1;
T[i][i-1] = 0;
}
for (j = 2; j <= n; ++j)
{
for (i = 0; i + j - 1 < n; ++i)
{
k = i + j -1;
if (s[i] == s[k] && T[i+1][k-1] == k-1-i)
{
T[i][k] = T[i+1][k-1] + 2;
}
else
{
T[i][k] = max(T[i+1][k], T[i][k-1]);
}
}
}
// Simple O(N**2) algo
public String getLargestPalindrome(final String input)
{
final int n = input.length();
for (int wordSize = n; wordSize >= 2; wordSize--)
{
for (int startPos = 0; startPos <= n - wordSize; startPos++)
{
final String checkWord = input.substring(startPos, startPos + wordSize);
System.out.println(checkWord);
if (isPalindrome(checkWord))
{
return checkWord;
}
}
}
return "<No palindrome was found>";
}
Step1: index 0=stIndx, index n=lstindx=length(string)-1.
Step2:check if string from stIndx to lstindx is palindrome, if yes abort and save the length, if no stindx to lstindx=lstindx-1 and check for palindrome again.
Step 3: Repeat step 2 till stIndx=lstIndx or you find a palindrome (whichever comes first)
Step4: Check if string from stIndx=stIndx+1 to lstIndx and check for palindrome.
Step 5: Repeat step 4 till you find a palindrome or stIndx =lstIndx (whichever comes first)
Step6: Compare the string obtained from step 3 and step 5, display the larger string.
Step1: index 0=stIndx, index n=lstindx=length(string)-1.
Step2:check if string from stIndx to lstindx is palindrome, if yes abort and save the length, if no stindx to lstindx=lstindx-1 and check for palindrome again.
Step 3: Repeat step 2 till stIndx=lstIndx or you find a palindrome (whichever comes first)
Step4: Check if string from stIndx=stIndx+1 to lstIndx and check for palindrome.
Step 5: Repeat step 4 till you find a palindrome or stIndx =lstIndx (whichever comes first)
Step6: Compare the string obtained from step 3 and step 5, display the larger string.
public class LongestPalindrome {
public static void main(String[] args) {
String str = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println("Longest Palindrome: "+longestPalindrome(str));
}
public static String longestPalindrome(String str){
String longestPalindrome = null;
if(null==str)
return null;
else{
longestPalindrome=str.substring(0,1);
for(int i=0;i<str.length()-1;i++){
String palindrome=expand(str,i,i);
if(palindrome.length()>1)
System.out.println(palindrome);
if(palindrome.length()>longestPalindrome.length()){
longestPalindrome=palindrome;
}
palindrome=expand(str,i,i+1);
if(palindrome.length()>1)
System.out.println(palindrome);
if(palindrome.length()>longestPalindrome.length()){
longestPalindrome=palindrome;
}
}
}
return longestPalindrome;
}
static String expand(String str, int left, int right){
if(left>right)
return null;
else{
while(left>=0 && right<str.length()&&str.charAt(left)==str.charAt(right)){
right++;
left--;
}
}
return str.substring(left+1,right);
}
}
In C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LargestCommonSubstring
{
class Program
{
static void Main(string[] args)
{
var str = "ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD";
var longestPalindrome = GetLongestPalindrome(str);
Console.WriteLine(longestPalindrome);
}
public static string GetLongestPalindrome(string input)
{
int rightIndex = 0, leftIndex = 0;
List<string> paliList = new List<string>();
string currentPalindrome = string.Empty, longestPalindrome = string.Empty;
for (int currentIndex = 1; currentIndex < input.Length - 1; currentIndex++)
{
leftIndex = currentIndex - 1;
rightIndex = currentIndex + 1;
while (leftIndex >= 0 && rightIndex < input.Length)
{
if (input[leftIndex] != input[rightIndex])
{
break;
}
currentPalindrome = input.Substring(leftIndex, rightIndex -leftIndex + 1);
paliList.Add(currentPalindrome);
leftIndex--;
rightIndex++;
}
}
var x = (from c in paliList
select c).OrderByDescending(w=>w.Length).First();
return x;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace test
{
public class Program
{
static void Main(string[] args)
{
string s = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
String str="";
char[] a = s.ToCharArray();
for (int j = 0; j < a.Length; j++)
{
String tempchar = a[j].ToString();
for (int temp = j+1; temp < a.Length; temp++)
{
tempchar = String.Concat(tempchar, a[temp]);
if (ispalindrome(tempchar))
{
if (tempchar.Length > str.Length)
{
str = tempchar;
}
}
}
}
Console.WriteLine(str);
Console.ReadLine();
}
public static bool ispalindrome(string s1)
{
char[] arr = s1.ToCharArray();
Array.Reverse(arr);
string s2 = new String(arr);
if (s1.Equals(s2) == true)
{
return true;
}
return false;
}
}
}
Here is the solution using recursion. I think it is very easy to understand. feel free to share any pros and cons of the code.
public class longestpalindrome {
List<String> list = new ArrayList<String>();
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="ABCDCBAUVUCBALKJKLABC";
longestpalindrome obj = new longestpalindrome();
obj.maxpalindrome(s);
int max=1;
String s2="";
for(String s1 : obj.list){
if(s1.length()>max){
max=s1.length();
s2=s1;
}
}
if(s2.isEmpty())
System.out.println("No palindrome available");
else
System.out.println("Longest palindrome is "+s2);
}
void maxpalindrome(String s){
longestpalindrome obj1 = new longestpalindrome();
if(obj1.checkpalindrome(s) && s.length()>1){
list.add(s);
}
else{
if(s.length()>1){
maxpalindrome(s.substring(1));
maxpalindrome(s.substring(0,s.length()-1));
}
}
}
boolean checkpalindrome(String s){
int i=0;
int j=s.length()-1;
while(i<=j){
if(s.charAt(i)==s.charAt(j)){
i++;
j--;
}
else
return false;
}
return true;
}
}
public string LargestPalindrome (string str)
{
string maxPoli = String.Empty;
char[] chArray = str.ToCharArray();
for(int i=0;i<str.Length;i++)
{
var val = Expand(chArray,i);
if (maxPoli.Length < val.Length) maxPoli = val;
}
return maxPoli;
}
private string Expand(char[] str ,int index)
{
string tempval = String.Empty;
for(int i=index, j=index; i>-1; i--,j++)
{
if (j< str.Length && str[i] == str[j]) tempval = new string(str, i, j - i+1);
else break;
}
return tempval.Length>1 ? tempval :String.Empty;
}
package oracle.string.examples;
public class PalindromesInString {
public static void main(String[] args) {
String givenStr ="MADAMABABKALOMORAKMADAM";
PalindromesInString pal = new PalindromesInString();
String result = pal.getBiggestPalindrome(givenStr);
System.out.println("Result :"+result);
}
String getBiggestPalindrome(String str) {
String revStr = new StringBuffer(str).reverse().toString();
String biggestPalindrome = "";
for (int i = 0; i < str.length(); i++) {
char tempChar = str.charAt(i);
for (int j = i+1; j < str.length(); j++) {
char nextChar=str.charAt(j);
if(tempChar==nextChar){
String tempString = str.substring(i, j+1);
if(biggestPalindrome.length()<tempString.length() && revStr.contains(tempString)){
biggestPalindrome =tempString;
}
}
}
}
return biggestPalindrome;
}
}
A simple Groovy algorithm which runs in O(n**2). Look for palindromes starting from the center. Note that the center might be on character (in case the palindrome length is odd - aba) or between two characters (when the palindrome length is even aabbaa).
The most efficient solution would be the Manacher’s algorithm, which runs in O(n), but is too complex for me.
def run() {
expect:
getLongestPalindromeSubsequence(string) == result
where:
string | result
"a010c" | "010"
"abc" | "a"
"a001100" | "001100"
"" | ""
"0aa1bb2" | "aa"
}
def getLongestPalindromeSubsequence(String string) {
if(string.length() == 0) {
return ""
}
char[] s = string.toCharArray()
int first = 0
int last = 0
// Look for palindromes with odd length starting from the center
for(int i = 1; i < string.length() - 1; i++) {
int i_l = i-1, i_r = i+1
while(i_l >= 0 && i_r < string.length() && s[i_l] == s[i_r]) {
i_l--
i_r++
}
i_r--
i_l++
if(i_r-i_l > last-first) {
last = i_r
first = i_l
}
}
// Look for palindromes with even length starting from the center (between two chars)
// i = the first character to the left of the center
for(int i = 1; i < string.length() - 1; i++) {
int i_l = i, i_r = i+1
while(i_l >= 0 && i_r < string.length() && s[i_l] == s[i_r]) {
i_l--
i_r++
}
i_r--
i_l++
if(i_r-i_l > last-first) {
last = i_r
first = i_l
}
}
return string.substring(first, last+1)
}
#include <stdio.h>
#include<string.h>
int main(void) {
char str[100];
scanf("%s",str);
int len=strlen(str);
int j,k;
int lp[len][len];
for(j=0;j<len;j++)
for(k=0;k<len;k++)
lp[j][k]=-100;
for(k=0;k<len;k++)
for(j=0;j<len-k;j++)
{ if(j==j+k)
lp[j][j+k]=1;
else if(((lp[j+1][j+k-1]==k-1) || (k==1))&& strncmp(&str[j],&str[j+k],1)==0)
lp[j][j+k]=k+1;
else
{ if(lp[j+1][j+k]>lp[j][j+k-1])
lp[j][j+k]=lp[j+1][j+k];
else
lp[j][j+k]=lp[j][j+k-1];
}
}
printf("%d",lp[0][len-1]);
return 0;
}
ublic class LongestPalindrome {
public static void main(String []args){
int max=0;
int start=0;
int stop=0;
int maxIndex=0;
String given="abcdeedcbadgefdadadaddd";
String toreturn="";
for(int i=0;i<given.length();i++)
{
int a=i;
int j=i;
//This takes care of the unsymetric but same palindrones like ggggg
// if(i-1>=0 && i+1<given.length()-1){if(given.charAt(i+1)==given.charAt(i) && given.charAt(i)==given.charAt(i-1))j=i;}
//This takes care of symetricpalindromes like aeea and ggggg;
if(i+1<given.length()-1 && i-1>=0){if(given.charAt(i+1)==given.charAt(i) && given.charAt(i)!=given.charAt(i-1))j =i+1;}
int count=0;
while(a>=0 && j<given.length())
{
if(given.charAt(a) != given.charAt(j)) break;
count++;
if(max<count) {max=count;start=a;stop=j;maxIndex=i;}
a--;j++;
}
}
for(int m=start;m<stop+1;m++) toreturn +=given.charAt(m);
System.out.println(toreturn +""+ max + ""+ start + ""+ stop);
}
}
Public class LongestPalindrome {
public static void main(String []args){
int max=0;
int start=0;
int stop=0;
int maxIndex=0;
String given="abcdeedcbadgefdadadaddd";
String toreturn="";
for(int i=0;i<given.length();i++)
{
int a=i;
int j=i;
//This takes care of symetricpalindromes like aeea and ggggg;
if(i+1<given.length()-1 && i-1>=0){if(given.charAt(i+1)==given.charAt(i) && given.charAt(i)!=given.charAt(i-1))j =i+1;}
int count=0;
while(a>=0 && j<given.length())
{
if(given.charAt(a) != given.charAt(j)) break;
count++;
if(max<count) {max=count;start=a;stop=j;maxIndex=i;}
a--;j++;
}
}
for(int m=start;m<stop+1;m++) toreturn +=given.charAt(m);
System.out.println(toreturn );
}
}
Here is the answer
public void Run()
{
ArrayList result = this.FindBiggestPalindrome("abcracecarabamalayalamabcdefghgfedcba12351");
result = this.FindBiggestPalindrome("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD");
}
public ArrayList FindBiggestPalindrome(string input)
{
ArrayList stringlist = new ArrayList();
int inputfirstindex = 0;
int inputlastindex = input.Length - 1;
int counter = 0;
while (inputfirstindex < inputlastindex)
{
for (int count = inputfirstindex; count <= inputlastindex - inputfirstindex; count++)
{
if (this.IsPalindrome(input.Substring(inputfirstindex, input.Length - count - inputfirstindex)) && input.Substring(inputfirstindex, input.Length - count - inputfirstindex).Length > 1)
{
stringlist.Add(input.Substring(inputfirstindex, input.Length - count - inputfirstindex));
}
counter++;
}
inputfirstindex++;
}
Console.WriteLine("Counter = " + counter);
return stringlist; ;
}
public bool IsPalindrome(string input)
{
Console.WriteLine(input);
bool result = true;
int min = 0;
int max = input.Length - 1;
while (min < max)
{
//Console.WriteLine(input[min].ToString().ToLowerInvariant() + "==" + input[max].ToString().ToLowerInvariant());
if (input[min].ToString().ToLowerInvariant() != input[max].ToString().ToLowerInvariant())
{
result = false;
break;
}
min++; max--;
}
return result;
}
public class LongestPalindrome {
/**
* @param args //laxmikant's arena
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
longestPalindrome("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD");
}
public static void longestPalindrome(String str){
int len=str.length();
int[][] table=new int[len][len];
for(int i=0;i<len;i++)
{
for(int j=0;j<len;j++)
{
table[i][j]=0;
}
}
for(int i=0;i<len-1;i++)
{
table[i][i]=1;
if(str.charAt(i)==str.charAt(i+1))
table[i][i+1]=1;
}
table[len-1][len-1]=1;
int start=0,max_len=0;
for(int k=3;k<=len;k++)
{
for (int i=0;i<=len-k;i++)
{
int j=i+k-1;
if(table[i+1][j-1]==1 && str.charAt(i)==str.charAt(j))
{
table[i][j]=1;
if(k>max_len)
{
max_len=k;
start=i;
}
}
}
}
System.out.println(str.substring(start,start+max_len));
}
}
Ruby enabled me to develop a very succinct solution to this.
{{
#!/usr/bin/env ruby
class String
def largest_palindrome
s1 = self.split("")
s2 = s1.reverse
p = ""
(s2.length/2 + 1).times do |i|
# Determine the max length of aligned letters.
c = s1.each_with_index.collect do |v1,j|
v1 == s2[j] ? v1 : "_"
end
c = c.join.split("_")
n = c.collect{|e| e.length}.max || 0
p = c.find{|e| e.length == n} if n > p.length
s2.rotate!
end
p
end
end
s = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"
puts "Largest Palindrome: \"#{s.largest_palindrome}\""
}}
#!/usr/bin/env ruby
class String
def largest_palindrome
s1 = self.split("")
s2 = s1.reverse
p = ""
(s2.length/2 + 1).times do |i|
# Determine the max length of aligned letters.
c = s1.each_with_index.collect do |v1,j|
v1 == s2[j] ? v1 : "_"
end
c = c.join.split("_")
n = c.collect{|e| e.length}.max || 0
p = c.find{|e| e.length == n} if n > p.length
s2.rotate!
end
p
end
end
s = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"
puts "Largest Palindrome: \"#{s.largest_palindrome}\""
Sorry about the formatting problems...
#!/usr/bin/env ruby
class String
def largest_palindrome
s1 = self.split("")
s2 = s1.reverse
p = ""
(s2.length/2 + 1).times do |i|
# Determine the max length of aligned letters.
c = s1.each_with_index.collect do |v1,j|
v1 == s2[j] ? v1 : "_"
end
c = c.join.split("_")
n = c.collect{|e| e.length}.max || 0
p = c.find{|e| e.length == n} if n > p.length
s2.rotate!
end
p
end
end
s = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"
puts "Largest Palindrome: \"#{s.largest_palindrome}\""
Added missing validation step:
#!/usr/bin/env ruby
class String
def largest_palindrome
s1 = self.split("")
s2 = s1.reverse
p = ""
(s2.length-1).times do |i|
# Determine the max length of aligned letters.
c = s1.each_with_index.collect do |v1,j|
v1 == s2[j] ? v1 : "_"
end
c = c.join.split("_")
n = c.collect{|e| e.length}.max || 0
if n > p.length
p_new = c.find{|e| e.length == n}
# Validate that p_new is a palindrome.
p = p_new if p_new == p_new.reverse
end
s2.rotate!
end
p
end
end
s = ["abacdgfdcaba","ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"]
s.each do |s|
puts "Largest Palindrome: \"#{s.largest_palindrome}\""
end
#include <stdio.h>
#include <string.h>
main()
{
char buff[]="abaabacbcabafhaba";
int i,j,k,len,poly1=0,poly2=0,ppoly1=0,ppoly2=0,poly=-1,flag=0;
len = strlen(buff);
printf("%d\n",len);
for(i=0;(i<len)&&((len-i)>(ppoly2-ppoly1));i++) /* condition (len-i)>(ppoly2-ppoly1) for optimization in first loop*/
{
for(j=i,k=len-1;j<k;k--)
{
if(buff[j]==buff[k])
{
poly1=j;
poly2=k;
flag=(k-j)%2;
while(buff[j]==buff[k]&&(j<k))
{
k--;
j++;
}
if(((flag==0)&&(k==j))||(flag&&(j-k)==1))
{
if((poly2-poly1)>poly)
{
poly=poly2-poly1;
ppoly1=poly1;
ppoly2=poly2;
}
break; // for optimization in secon loop.
}
j= poly1;
k= poly2;
}
}
}
printf("Indexes are %d : %d \n Hence maximum length of polydr0n string is: %d", ppoly1,ppoly2,ppoly2-ppoly1+1);
}
public class LargestPanlindrom {
/**
* @param args
*/
public String palindrom(String str)
{
TreeSet st=new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length()>s2.length()?-11:1;
}
});
for(int i=0;i<str.length();i++)
{
String s="";
for(int j=i;j<str.length();j++)
{
s=s+str.charAt(j);
if(new StringBuffer(s).reverse().toString().equals(s)){
if(s.length()>=3)
st.add(s);
}
}
}
System.out.println(st);
return st.first().toString();
}
public static void main(String[] args) {
String str="ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println("Longest Panlindrom "+new LargestPanlindrom().palindrom(str));
}
}
public class LargestPanlindrom {
/**
* @param args
*/
public String palindrom(String str)
{
String large="";
for(int i=0;i<str.length();i++)
{
String s="";
for(int j=i;j<str.length();j++)
{
s=s+str.charAt(j);
if(new StringBuffer(s).reverse().toString().equals(s)){
if(large.length()<s.length())
large=s;
}
}
}
return large;
}
public static void main(String[] args) {
String str="ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println("Longest Panlindrom "+new LargestPanlindrom().palindrom(str));
}
}
public class LargestPanlindrom {
/**
* @param args
*/
public String palindrom(String str)
{
String large="";
for(int i=0;i<str.length();i++)
{
String s="";
for(int j=i;j<str.length();j++)
{
s=s+str.charAt(j);
if(new StringBuffer(s).reverse().toString().equals(s)){
if(large.length()<s.length())
large=s;
}
}
}
return large;
}
public static void main(String[] args) {
String str="ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println("Longest Panlindrom "+new LargestPanlindrom().palindrom(str));
}
}
public class LargestPanlindrom {
public String palindrom(String str) {
String large = "";
for (int i = 0; i < str.length(); i++) {
String s = "";
for (int j = i; j < str.length(); j++) {
s = s + str.charAt(j);
if (new StringBuffer(s).reverse().toString().equals(s)) {
if (large.length() < s.length())
large = s;}}}return large;}
public static void main(String[] args) {
String str = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println("Longest Panlindrom "
+ new LargestPanlindrom().palindrom(str));}}
How is the below code
please tell, is it optimize, not optimize?
improvisation
public class LargestPalindrome
{
/*Imagine we have a large string like this "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"
* which contains multiple palindromes within it, like ABCBA, RACECAR, ARA, IAMAI etc...
* Now write a method which will accept this large string and return the largest palindrome from
* this string. If there are two palindromes which are of same size, it would be sufficient
* to just return any one of them.*/
String word;
String largestPalindrome;
public LargestPalindrome()
{
word="ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
word=word.toLowerCase();
largestPalindrome="";
}
/**
* @param args
*/
public static void main(String[] args)
{
LargestPalindrome largestPalindrome=new LargestPalindrome();
largestPalindrome.printLargestPalindrome();
}
private void printLargestPalindrome()
{
for(int j=0;j<word.length();j++)
{
int nextPos=findPosNextMatchingCharacter(j, word.charAt(j));
// System.out.println("word.charat "+ word.charAt(j)+" ,next pos="+nextPos+" currPos="+j);
if(nextPos!=-1)
{
//doing nextPos+1 is because substring is next position exclusive
String portionOfWord=word.substring(j, nextPos+1);
// System.out.println("Portion of word "+portionOfWord);
if(findIfPalindrome(portionOfWord.trim()))
{
// System.out.println("Is Palindrome "+portionOfWord);
if(portionOfWord.length()>largestPalindrome.length())
{
largestPalindrome=portionOfWord;
}
}
}
}
System.out.println("Largest palindrome="+largestPalindrome);
}
int findPosNextMatchingCharacter(int currPos,char input)
{
int pos=-1;
currPos=currPos+1;
for(;currPos<word.length();currPos++)
{
if(word.charAt(currPos)==input)
{
pos=currPos;
currPos=word.length();
}
}
return pos;
}
boolean findIfPalindrome(String input)
{
boolean palindrome=false;
String reverse=reverseTheWord(input);
palindrome=input.equalsIgnoreCase(reverse);
return palindrome;
}
private String reverseTheWord(String input)
{
StringBuilder reverse=new StringBuilder();
int i=input.length()-1;
for(;i>=0;i--)
{
reverse.append(input.charAt(i));
}
return reverse.toString();
}
}
all palindrome has a reflexive point of AA or ABA.
0) Return error if string is null or empty. Return the source string if length is 1.
1) Find the reflexive point (r): iterate and save reflective r location if source[i]==source[i+1] or source[i-1]==source[i+1]
2) Expand the string from the reflexive point r:
if ((r+toRight) > 0 and (r+toLeft)<string.Length) and if (string[r+toRight] equals string[r+toLeft])
result=source[r+toLeft] + result + source[r+toRight]
3) Repeat 1 to find next r and Repeat 2 build the next palindrome and replace the existing one if the length of the new palindrome is longer.
4) Return the saved palindrome/
public class polindrom2 {
private int largetsPolindrom(String str) {
// str=str.toLowerCase();
StringBuffer sb = new StringBuffer();
int counter = 0;
int middleCharacter = 0;
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i));
String restoftheString = str.substring(i + 1, str.length());
StringBuffer reverse = new StringBuffer(sb);
CharSequence ch = reverse.reverse();
if (restoftheString.contains(ch)) {
if (sb.length() > counter) {
if (!str.contains(sb + ch.toString())) { // if the (sb=AB) +( ch=BA) = ABBA is str then it means that there is no character in the middle ,otherwise it ABCBA
middleCharacter = 1;
} else {
middleCharacter = 0;
}
counter = sb.length();
}
} else {
sb = new StringBuffer();
}
}
return counter * 2 + middleCharacter;
}
str = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"
palList = []
tempList =[]
tempStr = ""
tmp=""
count = 0
n=2
for c in str:
if c in tempList:
if count-n >= 0 and c == str[count-n]:
tmp = str[count-n:count+1]
tempList.append(c)
count +=1
n +=2
continue
if tmp !="":
palList.append(tmp)
tmp = ""
tempList.append(c)
count +=1
n = 2
palStr =""
maxLen = 0
for pal in palList:
if len(pal) > maxLen:
maxLen = len(pal)
palStr = pal
print "longest palindrome is :" , palStr
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char str[]={'A','B','C','B','A','H','E','L','L','O','H','O','W','R','A','C','E','C','A','R','A','R','E','Y','O','U','I','A','M','A','I','D','O','I','N','G','G','O','O','D'},temp[10];
int i=strlen(str),j,k,c=0,a,b,count=0,n,l=0;
for(n=0;n<i-1;n++)
{
j=n;
k=i-1;
for(;k>j;k--)
{
a=j;
b=k;
while(a!=b || a<b)
{
if(str[a]==str[b])
{
a++;
b--;
}
else
break;
}
if(a==b)
{
c=k-j+1;
if(count<c)
{
count=c;
for(l=0;j+l<=k;l++)
temp[l]=str[j+l];
}
}
}
}
if(l==0)
printf("every element is different");
else
{
for(n=0;n<l;n++)
printf("%c",temp[n]);
}
getch();
}
import java.util.ArrayList;
public class CheckMultPalendrms {
public static void main(String[] args) {
String str="ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
int n=str.length();
ArrayList<String> arl=new ArrayList<String>();
String max="";
for (int i = 1; i < n-1; i++) {
int it=1;
if(str.charAt(i-it)!=-1){
while(str.charAt(i-it)==str.charAt(i+it)){
String strg=str.substring(i-it, i+(it+1));
arl.add(strg);
it++;
if(i<it){
break;
}
}
}
}
for (String strg : arl) {
int strlen=strg.length();
int maxlen=max.length();
if (strlen>maxlen) {
max=strg;
}
}
System.out.println("Max palindrom is "+max);
}
}
public class Longest_Palindromic_Substring
{
public static void main(String []args)
{
Longest_Palindromic_Substring obj = new Longest_Palindromic_Substring();
System.out.println(obj.LONGESTstringPALIDROME("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"));
}
private String LONGESTstringPALIDROME(String string)
{
if(string.isEmpty())
{
return null;
}
if(string.length()==1)
{
return string;
}
String longest = string.substring(0,1);
for(int i =0;i<string.length();i++)
{
String tmp = checker(string,i,i);
if(tmp.length()>longest.length())
{
longest = tmp;
}
tmp = checker(string,i,i+1);
if(tmp.length()>longest.length())
{
longest = tmp;
}
}
return longest;
}
private String checker(String string, int begin, int end)
{
while (begin>=0 && end <= string.length() -1 && string.charAt(begin) == string.charAt(end))
{
begin--;
end++;
}
return string.substring(begin+1,end);
}
}
public class Longest_Palindromic_Substring
{
public static void main(String []args)
{
Longest_Palindromic_Substring obj = new Longest_Palindromic_Substring();
System.out.println(obj.LONGESTstringPALIDROME("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD"));
}
private String LONGESTstringPALIDROME(String string)
{
if(string.isEmpty())
{
return null;
}
if(string.length()==1)
{
return string;
}
String longest = string.substring(0,1);
for(int i =0;i<string.length();i++)
{
String tmp = checker(string,i,i);
if(tmp.length()>longest.length())
{
longest = tmp;
}
tmp = checker(string,i,i+1);
if(tmp.length()>longest.length())
{
longest = tmp;
}
System.out.println(tmp);
}
return longest;
}
private String checker(String string, int begin, int end)
{
while (begin>=0 && end <= string.length() -1 && string.charAt(begin) == string.charAt(end))
{
begin--;
end++;
}
return string.substring(begin+1,end);
}
}
C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LargestPalindrome
{
class Program
{
static void Main(string[] args)
{
FindPalindrome("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD");
}
public static void FindPalindrome(String str)
{
Char[] cActualArr = str.ToCharArray();
String sOriginal = cActualArr[0].ToString();
int iMaxleng = 0;
String sLargestPalindrome = "";
for (int k = 1; k < cActualArr.Length; k++)
{
for (int i = k; i < cActualArr.Length; i++)
{
sOriginal = sOriginal + cActualArr[i].ToString();
Char[] cTempArr = sOriginal.ToCharArray();
string sCompareStr = "";
for (int j = cTempArr.Length - 1; j >= 0; j--)
{
sCompareStr = sCompareStr + cTempArr[j].ToString();
}
if (sCompareStr.Equals(sOriginal))
{
if (iMaxleng < sOriginal.Length)
{
iMaxleng = sOriginal.Length;
sLargestPalindrome = sOriginal;
}
}
}
sOriginal = "";
}
Console.WriteLine("Largest palindrome is: " + sLargestPalindrome + " of length " + iMaxleng);
}
}
}
Ans: RACECAR
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(string s){
int i=0, j= s.length() - 1;
while(i<=j){
if(s.at(i) != s.at(j))
return false;
i++; j--;
}
return true;
}
int main(){
string s = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINEVERODDOREVENNGGOOD";
string s_temp;
string s_biggest_pal;
for(unsigned int i=0; i<s.length() - 1; i++){
s_temp.insert(s_temp.end(), s.at(i));
for(unsigned int j=i+1; j<s.length(); j++){
s_temp.insert(s_temp.end(), s.at(j));
bool result = isPalindrome(s_temp);
if(result && (s_temp.length() > s_biggest_pal.length())){
s_biggest_pal = s_temp;
}
}
s_temp.clear();
}
cout<<s_biggest_pal<<endl;
}
Output: NEVERODDOREVEN
public class Palindrome {
public static void main(String args[]){
Palindrome mypalindrome = new Palindrome();
String input1 = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
System.out.println(mypalindrome.largestPalindrome(input1));
}
public String largestPalindrome(String input){
for(int i = input.length()-1; i>=2; i--){
for(int j=0; j< input.length()-i; j++){
String mystr = input.substring(j,j+i);
if(isPalindrome(mystr)){
return mystr;
}
}
}
return "";
}
public Boolean isPalindrome(String input){
char[] inputchar = input.toCharArray();
for(int i =0; i < inputchar.length; i++){
if(inputchar[i] != inputchar[inputchar.length-1 -i]){
return false;
}
}
return true;
}
}
/*
*
* MAX_POLINDROME(str)
* for i 1 to length
* if current and current-1 matches //even length
* move both sides,count and check with max
* else if current and current-2 maches //odd length
* move both sides,count and check with max
*
* return the max length string
*
*/
- Dany March 12, 2014