# Length of the Longest Palindromic Substring [duplicate]

A palindrome is a string which is the same when read forwards and backwards. For example "racecar" is a palindrome, but "Racecar" is not. A substring is a contiguous set of characters in a larger string. Your task is to write a program or method which takes a string or character array as input and outputs the length of the longest substring of that string which is a palindrome.

Examples

Input

banana


Ouput

5


This is because "anana" is a 5 character substring of "banana"

Input

abracadabra


Output

3


This is because both "aca" and "ada" are 3 characters.

Input

True


Output

1


This string has no palindromes that are more than 1 character.

If the input is the empty string the output must be 0.

This is code-golf so the shortest submission in any language wins.

Note: There have been slight variations of this question in the past, which have all had wording issues or been asking a variation of this question. You can see these:

Find the Longest Palindrome in a String by Removing Characters

Longest reverse palindromic DNA substring

How do I find the longest palindrome in a string?

Finding "sub-palindromes". - The purpose of this challenge is to print all palindromic substring, rather than the length of the longest. As such many of the answers to this question do not have close analogues.

• Related, borderline dupe. My vote is a hammer, though, so I won't vote as yet. Feb 13, 2018 at 13:43
• codegolf.stackexchange.com/questions/16327/… is another, but it's not really another. Feb 13, 2018 at 13:50
• @MagicOctopusUrn only the size of it. After all the longest palindrome might not be unique. Feb 13, 2018 at 14:00
• Which are the valid input characters ? Feb 13, 2018 at 14:07
• @Bijan I usually golf this kind of thing using regexes. And if I substitute a string into a regex it's important to know if the characters can be regex metacharacters (like ., +, * etc) because just using them as is will cause errors. There is also the issue of spaces and newlines and how they are handled in I/O. Languages like C might worry about \0 etc. Feb 13, 2018 at 16:03

# Brachylog, 9 bytes

{s.↔}ᶠlᵐ⌉


Try it online!

### Explanation

{   }ᶠ       Find all…
s.            …substrings of the input…
.↔           …which are their own reverse
lᵐ     Map length
⌉    Max


# 05AB1E, 9 8 bytes

ŒʒÂQ}€gM


Try it online!

• Was just about to post this :) Feb 13, 2018 at 13:52
• @Emigna I know there was a 3-byter for "filter list to contain only palindromes"... Can't remember though. Feb 13, 2018 at 13:53
• Don't think I know a 3-byter for that. I was hoping that à would work, but unfortunately it goes alphabetically and not by length when used on strings. Feb 13, 2018 at 13:55
• @Emigna I was thinking ŒéR then "find first palindrome", or Œé and find last palindrome, cant seem to do that in 4 or less though. Feb 13, 2018 at 13:57
• Yeah, using é also ends up at 8 bytes. I feel like it is impossible to do the "outside" code in less than 4 and I don't see a way to do the filtering in less than 4 either. Other methods I've tried all end up at 8 or 9 as well. Unless I'm missing something, this feels optimal. Feb 13, 2018 at 14:17

# Pyth, 7 bytes

le_I#.:


Try it online!

### How?

le_I#.: – Full program.

.: – All contiguous non-empty subsequences.
#   – Keep those...
_I    – That are invariant under reversal.
e      – Get the last element.
l       – And take its length.


Note that the substrings are ordered by length, in Pyth.

• Do we know the last element is the longest (i.e. are the subsequences ordered by length)? Feb 13, 2018 at 15:03
• @TobySpeight Yes, in Pyth the substrings are ordered by length. Feb 13, 2018 at 15:03

# Jelly, 6 bytes

Saved 1 byte thanks to Dennis (pointing out that Þ is stable and thus works instead of Ðf).

ẆŒḂÞṪL


Try it online!

### How?

ẆŒḂÞṪL – Full program.

Ẇ      – All contiguous non-empty subsequences.
Þ   – Stable sort by...
ŒḂ    – 1 if the element is palindrome, 0 otherwise.
Ṫ  – Get the last element.
L – And take its length.


Note that the substrings are ordered by length, in Jelly.

• Since Jelly's sort is stable, you should be able to replace Ðf with Þ. Feb 13, 2018 at 15:19

# Java 8, 163 bytes

s->{int r=0,l=s.length(),i=0,j,T;for(String t;i<l;i++)for(j=i;++j<=l;r=t.contains(new StringBuffer(t).reverse())&(T=t.length())>r?T:r)t=s.substring(i,j);return r;}


Explanation:

Try it online.

s->{                 // Method with String parameter and integer return-type
int r=0,           //  Result-String, starting empty
l=s.length(),  //  The length of the input-String
i=0,j,         //  Index-integers
T;             //  Temp integer
for(String t;      //  Temp String
i<l;i++)       //  Loop i over the String
for(j=i;++j<=l;  //   Inner loop j over the String
r=           //     After every iteration, set the result to:
t.contains(new StringBuffer(t).reverse())
//      If the temp-String is a palindrome,
&(T=t.length())>r?
//      and the length of the substring is larger than the result
T         //       Set this length as the new result
:          //      Else:
r)        //       Keep the result the same
t=s.substring(i,j);
//    Set the temp String to the substring from index i to j
return r;}         //  Return the result


# Husk, 8 bytes

L►LfS=↔Q


Try it online!

### How?

L►LfS=↔Q – Full program.

Q – All contiguous non-empty subsequences.
f     – Keep those...
S=   – That are equal to themselves when...
↔  – Reversed.
►L      – Get the maximum element, sorted by length.
L        – Take its length.


Alternative: ▲mLfS=↔Q. Note that the substrings are not ordered by length, in Husk.

# Retina, 42 bytes

Lv(.)*.?(?<-1>\1)*(?(1)(?!))
N$^$.&
\G.


Try it online! Link includes test cases. Explanation:

Lv(.)*.?(?<-1>\1)*(?(1)(?!))


For each character in the string, find the longest palindrome that starts at that point.

N$^$.&


Sort the found palindromes in reverse order of length.

\G.


Count the length of the first (i.e. longest) palindrome.

# Python 3, 58 bytes

f=lambda s:len(s)if s==s[::-1]else max(f(s[1:]),f(s[:-1]))


Try it online!

• Nice answer, but you shouldn't answer so quickly :P I'd advise waiting it a week or so, however you can keep the answer if you want. Feb 13, 2018 at 13:58

# J, 20 bytes

[:>./@,#\(#*]-:|.)\]


Try it online!