## (Longest Palindromic Substring)

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 == s[s.size() - 1] &&
isPalindrome(s.substr(1,s.size()-2));
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910500a6b66', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910500a6b98',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910500a6b99',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. aroudakili
Mar 13, 2013 @ 15:57:43

I think line 5 (Java) must be :
String sub = s.substring(j, len);

• Runhe Tian
Mar 13, 2013 @ 16:03:47

No, 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:47

oh OK, I was working on C# I thought Substring in java is same as c# which takes start index and length.
Thanks

2. asdas
Jul 19, 2013 @ 00:56:43

gr8 solution

3. Qwerty
Jan 24, 2014 @ 22:08:30

Have you tried running this code? j + len gives String index out of bounds.