# 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 !!!

August 1, 2024

### Revolutionizing Your Ride: Expert Auto Service At Carolina Auto Service

February 27, 2024

January 25, 2024

January 25, 2024

January 24, 2024

January 19, 2024

01 Aug

27 Feb

25 Jan

25 Jan

24 Jan

19 Jan