Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

**Thoughts:**

Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

**Code (Java):**

public class Solution {
public String longestPalindrome(String s) {
for(int len = s.length(); len > 0; --len) {
for(int j = 0; j <= s.length() - len; ++j) {
String sub = s.substring(j, j + len);
if(isPalindrome(sub))
return sub;
}
}
return new String();
}
private boolean isPalindrome(String s) {
if(s.length() <= 1)
return true;
else
return s.charAt(0) == s.charAt(s.length()-1) &&
isPalindrome(s.substring(1,s.length()-1));
}
}

**Code (C++):**

class Solution {
public:
string longestPalindrome(string s) {
for(int len = s.size(); len > 0; --len) {
for(int i = 0; i <= s.size() - len; ++i) {
string sub = s.substr(i, len);
if(isPalindrome(sub))
return sub;
}
}
return "";
}
private:
bool isPalindrome(string s) {
if(s.size() <= 1)
return true;
else
return s[0] == s[s.size() - 1] &&
isPalindrome(s.substr(1,s.size()-2));
}
};

### Like this:

Like Loading...

*Related*

aroudakili

Mar 13, 2013@ 15:57:43I think line 5 (Java) must be :

String sub = s.substring(j, len);

Runhe Tian

Mar 13, 2013@ 16:03:47No, the signature of substring method for String class is:

substring(int beginIndex, int endIndex)

I’m extracting a substring that starts at j and ends at j + len, with a total length of “len”. Is that clear?

aroudakili

Mar 13, 2013@ 16:11:47oh OK, I was working on C# I thought Substring in java is same as c# which takes start index and length.

Thanks

asdas

Jul 19, 2013@ 00:56:43gr8 solution

Qwerty

Jan 24, 2014@ 22:08:30Have you tried running this code? j + len gives String index out of bounds.