# Algorithms {Longest Palindromic Substring}

Today we will talk about “Longest Palindromic Substring” problem. I’ve developed solution about year ago but a few days remembered it and thought about it.

So, full problem description:

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.

Ok, good, on the face of it, we can use some simple naive algorithm with O^2 complexity and problem will be solved. Good … But how we can check borders of the longest palindromic substring ? Oh, that is very interesting 🙂

For example we have string aba, we can use something like level order traversing and, yes, it would be BFS is not it ??? Execution steps like that :

•  index on a; try to left – null, try to right – not null; result is not palindrome; increase index;
•  index on b; try to left – a, try to right a, good, next level, left and right – nulls , good, palindrome; store to max palindromic instance; increment index;
• and so on ..

OK, it’s working on simple string. What about bb string ? …

Hm, if we start from b we can get just b as max substring but we should return bb … Interesting…

Naturally we can/should check index i and i+1 and compare result, is not it ? I think so, OK, try to write and submit code to leetcode 🙂

```public class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 1)
return s;

String longest = s.substring(0, 1); // first char

for(int i = 0; i < s.length(); i++){
String tempSubstring = substring(i, i, s);

if(longest.length() < tempSubstring.length()){
longest = tempSubstring;
}

tempSubstring = substring(i, i+1, s);

if(longest.length() < tempSubstring.length()){
longest = tempSubstring;
}
}
return longest;
}

String substring(int i, int j, String s){
while(i >=0 && j<s.length() && s.charAt(i) ==s.charAt(j)){
i--;
j++;
}
return s.substring(i+1, j);
}
}```

I’ve tried and it’s working 🙂

Good and thanks !!!