Find The Longest Palindrome In A String
October 15, 2010
Greplin issued a programming challenge recently that required programmers to solve three problems; when completed, Greplin issued an invitation to send them a resume. The first problem required the programmer to find the longest palindrome in the following 1169-character string:
Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
forustobeherededicatedtothegreattdafskremainingbeforeusthat
fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
olvethatthesedeadshallnothavediedinvainthatthisnationunsder
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth
Your task is to write a function that finds the longest palindrome in a string and apply it to the string given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Could someone delete my previous comment please ?
I tried the naive way. I don’t know much about palindrome.
oops my pastebin does not show up. my solution
[…] today’s Programming Praxis exercise, our goal is to write an alogrithm to find the longest palindrome in a […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/10/15/programming-praxis-find-the-longest-palindrome-in-a-string/ for a version with comments):
import qualified Data.ByteString.Char8 as B import qualified Data.List.Key as K longestPalindrome :: B.ByteString -> B.ByteString longestPalindrome s = K.maximum B.length [p | p <- B.inits =<< B.tails s, p == B.reverse p]Remco: I also used the O(n^3) algorithm when I solved the challenge; I wrote the code as fast as I can type, it worked the first time, and once I had the answer I moved on to the second level. But after I finished the challenge I went looking for a better way, and Jeuring’s solution was so pretty I had to include it in an exercise.
By the way, the second level was easy, involving fibonacci numbers, prime checking and integer factorization; I could have stolen code from several of our earlier exercises to solve it quickly, but instead I looked up the prime fibonacci numbers on OEIS and used Dario Alpern’s applet for the factorization. The third level involved generating all possible subsets and testing them for a particular condition, and the brute-force solution took over a minute to run. I’ve since got a much better solution for the third level, but I’m still looking for the “perfect” solution that I can use for an exercise.
Phil
My solution in Python:
I took the greplin challenge a few days ago too. Here was
my solution to problem 1. It’s O(n**2) in the worst case
but much closer to O(n) for typical input data.
#!/usr/bin/python txt = open('gettysburg.txt').read() longest = '' def nominate(s): global longest if len(s) > len(longest): longest = s def explore(i, j): """[i..j] is closed interval""" while 0 <= i and j < len(txt) and txt[i] == txt[j]: i -= 1 j += 1 nominate(txt[i+1:j]) # Odd-length substrings for i in range(1, len(txt) - 1): explore(i, i) # Even-length substrings for i in range(1, len(txt)): explore(i - 1, i) print longestThis file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
longest_palindrome.rb
hosted with ❤ by GitHub
#!/usr/bin/env ruby def longest_palindrome_in(string) palindrome = "" 0.upto string.length do |outer| string.length.downto outer+1 do |inner| forward = string.slice(outer..inner) if forward.length > palindrome.length && forward.eql?(forward.reverse) palindrome = forward end end end palindrome end string = DATA.read.gsub "\n", "" string.downcase! puts longest_palindrome_in string __END__ Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta inentanewnationconceivedinzLibertyanddedicatedtotheproposit ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh avecometodedicpateaportionofthatfieldasafinalrestingplacefo rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog etherfangandproperthatweshoulddothisButinalargersensewecann otdedicatewecannotconsecratewecannothallowthisgroundThebrav elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI tisforusthelivingrathertobededicatedheretotheulnfinishedwor kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather forustobeherededicatedtothegreattdafskremainingbeforeusthat fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres olvethatthesedeadshallnothavediedinvainthatthisnationunsder Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb ythepeopleforthepeopleshallnotperishfromtheearthI also did the slow and steady method. O(n^3) isn’t bad for 1169 characters, but it won’t be great for larger data. Small speed up: in my flp() function, starting case is a single character, so we begin by only searching for palindromes of length 2 or greater.
#!/usr/bin/env python # Find the longest palindrome in a given text def is_pal(s): return s == s[::-1] def flp(s): longest, len_longest = 'g', 1 for i in xrange(len(s)): for j in xrange(2,len(s[i:])): sub_s = s[i:i+j+1] if is_pal(sub_s) and len(sub_s) > len_longest: longest, len_longest = sub_s, j+1 return (longest, len_longest) def main(): f = open('four_score.txt') lines = ''.join(l for l in f.read().split()) f.close() pal, length = flp(lines) print "Length of longest palindrome:\t%s" % length print "Longest palindrome:\t%s" % pal return if __name__ == '__main__': main()And here’s my go at the O(n^2) solution described in the post, in Ruby:
#!/usr/bin/env ruby class PalindromeFinder def self.find(string) longest = "" (0...string.length).each do |count| palindrome = find_longest_palindrome_at_char string, count longest = palindrome if !palindrome.nil? && palindrome.length > longest.length end longest end # Return the longest palindrome in the given string using the character # at the position given as the midpoint of the search string. def self.find_longest_palindrome_at_char(string, position) max_string = string.slice 0..position found = nil (1..max_string.length/2).each do |count| potential = mid max_string, count return found unless palindrome? potential found = potential end found end # Return the middle of the given string, # counting count characters left and right. def self.mid(string, count) length = string.length mid = length / 2 start_pos = mid - count end_pos = string.length.even? ? mid + (count - 1) : mid + count puts "ERROR #{string} #{count} #{mid} #{start_pos} #{end_pos}" if start_pos < 0 || end_pos >= length string.slice start_pos..end_pos end # Return true if the given string is a palindrome. def self.palindrome?(string) true if !string.nil? && string.eql?(string.reverse) end end string = DATA.read.gsub "\n", "" string.downcase! puts PalindromeFinder::find string __END__ Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta inentanewnationconceivedinzLibertyanddedicatedtotheproposit ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh avecometodedicpateaportionofthatfieldasafinalrestingplacefo rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog etherfangandproperthatweshoulddothisButinalargersensewecann otdedicatewecannotconsecratewecannothallowthisgroundThebrav elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI tisforusthelivingrathertobededicatedheretotheulnfinishedwor kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather forustobeherededicatedtothegreattdafskremainingbeforeusthat fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres olvethatthesedeadshallnothavediedinvainthatthisnationunsder Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb ythepeopleforthepeopleshallnotperishfromtheearthHurray for leaving debugging code in the post >.<
txt=”’FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”’
palins=[]
def palindrome():
for i in range(len(txt)-1):
#print “iteration:”+str(i)
j=len(txt)-1
while(j>=i):
#check plaindrome
temp=txt[i:j]
last=len(temp)-1
iters=int(len(temp)/2)
flag=True
for n in range(iters):
if temp[n]!=temp[last-n]:
flag=False
break
if flag==True:
palins.append(temp)
j-=1
def getmax(li):
longest=”
for i in li:
if len(i) > len(longest):
longest=i
return (longest,len(longest))
palindrome()
print “longest palindrome: %s, size:%d” % getmax(palins)
O(n^2) solution in Scheme
; range (define make-range cons) (define range-from car) (define range-to cdr) (define (range-length r) (- (range-to r) (range-from r))) ; vector[from, to) -> string (define (subvector->list v range) (define (s->l from to) (if (>= from to) (list) (cons (vector-ref v from) (s->l (+ 1 from) to)))) (s->l (range-from range) (range-to range))) ; palindrome stuff (define (longest-palindrome-range v) ; v[first] == vector[second] (define (pal-pair? first second) (if (or (< first 0) (>= second (vector-length v))) #f (eq? (vector-ref v first) (vector-ref v second)))) ; longest palindrome range for position (define (range-for pos) (define (range-int from to) (if (pal-pair? from to) (range-int (- from 1) (+ to 1)) (make-range (+ from 1) to))) (let ((odd-p (range-int pos pos)) (even-p (range-int pos (+ pos 1)))) (if (> (range-length odd-p) (range-length even-p)) odd-p even-p))) ; search (define (longest-int from current-answer) (if (>= from (vector-length v)) current-answer (let ((candidate (range-for from))) (if (> (range-length candidate) (range-length current-answer)) (longest-int (+ 1 from) candidate) (longest-int (+ 1 from) current-answer))))) (longest-int 0 (make-range 0 0))) (define (longest-palindrome str) (let* ((v (list->vector (string->list str))) (range (longest-palindrome-range v))) (list->string (subvector->list v range)))) ; usage (longest-palindrome "problem string")> I’m still looking for the “perfect” solution that I can use for an exercise
solution based on coin change algorithm gives an answer almost instantly.
Here’s the O(n^2) solution in Matlab:
function longest_palindrom_quad()
%O(n^2) solution
txt = [‘Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta’ …
‘inentanewnationconceivedinzLibertyanddedicatedtotheproposit’ …
‘ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa’ …
‘rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic’ …
‘atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh’ …
‘avecometodedicpateaportionofthatfieldasafinalrestingplacefo’ …
‘rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog’ …
‘etherfangandproperthatweshoulddothisButinalargersensewecann’ …
‘otdedicatewecannotconsecratewecannothallowthisgroundThebrav’ …
‘elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove’ …
‘ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl’ …
‘ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI’ …
’tisforusthelivingrathertobededicatedheretotheulnfinishedwor’ …
‘kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather’ …
‘forustobeherededicatedtothegreattdafskremainingbeforeusthat’ …
‘fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh’ …
‘ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres’ …
‘olvethatthesedeadshallnothavediedinvainthatthisnationunsder’ …
‘Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb’ …
‘ythepeopleforthepeopleshallnotperishfromtheearth’];
n = length(txt);
palindrom_length = -inf;
palindrom = [];
for idx = 1:n
[odd_found, odd_span] = extend_odd(idx);
if odd_found
odd_len = 2*odd_span+1;
if odd_len > palindrom_length
palindrom = [idx – odd_span, idx + odd_span];
palindrom_length = odd_len;
end
end
[even_found, even_span] = extend_even(idx);
if even_found
even_len = 2*even_span;
if even_len > palindrom_length
palindrom = [idx – (even_span-1), idx + even_span];
palindrom_length = odd_len;
end
end
end
disp([‘palindrom is ‘ txt(palindrom(1):palindrom(2)) ]);
disp([‘length is ‘ num2str(palindrom_length)]);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [odd_found, odd_span] = extend_odd(odd_i)
flag = false;
oi = 1;
while(odd_i – oi >= 1 && odd_i + oi <= n)
if txt(odd_i – oi) == txt(odd_i + oi)
flag = true;
else
break;
end
oi = oi + 1;
end
if flag
odd_found = true;
odd_span = oi-1;
else
odd_found = false;
odd_span = nan;
end
end
function [even_found, even_span] = extend_even(even_i)
flag = false;
oi = 1;
while(even_i – (oi – 1) <= n && even_i + oi <= n)
if txt(even_i + oi) == txt(even_i – (oi – 1))
flag = true;
else
break;
end
oi = oi + 1;
end
if flag
even_found = true;
even_span = oi-1;
else
even_found = false;
even_span = nan;
end
end
end
Here is a solution in golang. It runs pretty fast, just 0.1 s
to compile, link, and run, in a Linux inside VirtualBox.
You can run it on golang.org.
(It took substantially longer time to write. This is my first program in golang.)
package main func main() { input := "Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta"+ "inentanewnationconceivedinzLibertyanddedicatedtotheproposit"+ "ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa"+ "rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic"+ "atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh"+ "avecometodedicpateaportionofthatfieldasafinalrestingplacefo"+ "rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog"+ "etherfangandproperthatweshoulddothisButinalargersensewecann"+ "otdedicatewecannotconsecratewecannothallowthisgroundThebrav"+ "elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove"+ "ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl"+ "ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI"+ "tisforusthelivingrathertobededicatedheretotheulnfinishedwor"+ "kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather"+ "forustobeherededicatedtothegreattdafskremainingbeforeusthat"+ "fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh"+ "ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres"+ "olvethatthesedeadshallnothavediedinvainthatthisnationunsder"+ "Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb"+ "ythepeopleforthepeopleshallnotperishfromtheearth" var palin string for i := 0; i < len(input) - 1; i++ { palin = larger(palin, input, i, i) palin = larger(palin, input, i, i+1) } println("Max palin: ", palin) } func larger(palin string, s string, i int, j int) string { var p = getPalin(s, i, j) if len(p) > len(palin) { return p } return palin } func getPalin(s string, i int, j int) string { for i >= 0 && j < len(s) && s[i] == s[j] { i-- j++ } i++ // adjust start index, end index is fine return s[i:j] // return palindrome }http://pastebin.com/embed_iframe.php?i=SiiKi8Yp
[…] Find the Longest Palindrome in a string: […]
Here is a more challenging test-case for your algorithms:
In the collected works of Shakespeare, there are 3 palindromes of 15 characters each — no Shakespearean palindrome is longer. Two are the phrase “Madam, madam, madam.” which is fairly easy to find. What’s the third?
[…] sure how I came across the Programming Praxis blog, but one of their recent posts caught my eye: find the longest palindrome in a string. Given a string, what is the longest palindrome contained in that string? I thought about it […]
Here is a solution in Factor:
http://re-factor.blogspot.com/2010/10/longest-palindrome.html
Mine in F#
let isPalindrome (s:string) = List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray())) let rec longest_palin_from_start (s:string) = if (isPalindrome s) then s else let length = s.Length longest_palin_from_start (s.Substring(0, length-1)) let rec longest_palin_in_string (s:string) = if (s.Length = 1) then s else let tt = longest_palin_from_start s let ttt = longest_palin_in_string (s.Substring(1)) if (tt.Length > ttt.Length) then tt else tttMine in F#
let isPalindrome (s:string) = List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray())) let rec longest_palin_from_start (s:string) = if (isPalindrome s) then s else let length = s.Length longest_palin_from_start (s.Substring(0, length-1)) let rec longest_palin_in_string (s:string) = if (s.Length = 1) then s else let tt = longest_palin_from_start s let ttt = longest_palin_in_string (s.Substring(1)) if (tt.Length > ttt.Length) then tt else tttmy C implementation
http://codepad.org/Rcp5KmqC</a.
my C implementation
http://codepad.org/Rcp5KmqC
def substrings(s): """ Yields substrings from string s in descending order """ l = len(s) for end in xrange(l, 0, -1): for start in xrange(l-end+1): yield s[start:start + end] def palindrome(s): return s == s[::-1] def longest_palindrome(s): for e in substrings(s): if palindrome(e): return edef longest_palindrome(S):
longest, n = ”, len(S)
if n = 0 and j < n:
if S[i] == S[j]:
L.append(S[i])
else:
break
i -= 1
j += 1
if L:
return ''.join(L[::-1] + M + L)
return ''
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CountPalindrome
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(“please input a string: “);
string test = Convert.ToString(Console.ReadLine());
Console.WriteLine(“the longest palindrome is ” + LongestPalindrome(test));
Console.ReadLine();
}
protected static int LongestPalindrome(string str)
{
int i = 0;
int j = 1;
int oldJ = 1;
int intMax = 1;
int intCount = 0;
if (str.Length == 0) return 0;
if (str.Length == 1) return 1;
int[] intDistance = new int[2] {0,1};
for( int k = 0; k < intDistance.Length; k++ ){
j = 1 + intDistance[k];
oldJ = j;
intCount = 0;
i = 0;
while (j = 0 && j b) return a; return b;
}
}
}
Reblogged this on rajispassionate.
Here’s the solution in O(n^2) : “ranynar”
https://github.com/huei90/leetcode-js/longest-palindrome-substring.js
“`
(function () {
var expandAroundCenter = function expandAroundCenter(s, c1, c2) {
var l = c1,
r = c2,
n = s.length;
while (l >= 0 && r <= n – 1 && s[l] == s[r]) {
l–;
r++;
}
return s.substr(l + 1, r – l – 1);
};
var longestPalindromeSimple = function longestPalindromeSimple(s) {
var n = s.length;
if (n == 0) {
return '';
}
var longest = s[0]; // a single char itself is a palindrome
for (var i = 0; i longest.length) {
longest = p1;
}
var p2 = expandAroundCenter(s, i, i + 1);
if (p2.length > longest.length) {
longest = p2;
}
}
return longest;
};
longestPalindromeSimple(‘bananad’); // => anana
// such as Tragedy @@
})();
“`
public class LongestPalindromicSubstring {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(longestPalindrome(“FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”));
}
public static String longestPalindrome(String s) {
String maxStr = “”;
for(int i = s.length();i >= 0;i –){
maxStr = isPalindrom(s, i);
if(maxStr.length() !=0)
break;
}
return maxStr;
}
public static String isPalindrom(String s,int len){
int i = 0;
StringBuffer str = new StringBuffer(s);
String str1;
String str2;
String str3 = “”;
while(i + len <= s.length()){
str1 = str.substring(i,i + len).toString();
StringBuffer str4 = new StringBuffer(str1);
str2 = str4.reverse().toString();
if(str1.equals(str2) && str3.length() < str1.length()){
str3 = str1;
break;
}
else{
i ++;
}
}
return str3;
}
}