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