Problem Statement

Given a string, Find the longest palindromic substring.

Solution Explanation

Understanding the question here is very simple, given a string RENTNOW, the substring NTN is a palindrome of length 3, and that would be the result.

Brute Force

Before we think of any optimized solutions, let's see how we can brute force this to find the longest palidromic substring.

My first intution is to start from each character and check for all substrings from that character. So when you start from R the substrings would be,

R E N T N O W
R, RE, REN, RENT, RENTN, RENTO, RENTOW

None of the above are palindromes except the single character R of course. So we can keep R as the current max palindrome and continue doing the same for all other characters.

The time complexity for this would be O(n^3), since we will be using two loops to accomplish this. Below is the java solution for longest palindromic substring.

class Solution {
    public String longestPalindrome(String s) {
        String max_str = "";
        int maxlen = 0;
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                if(isPalindrome(s.substring(i, j+1))){
                    if((j+1-i)>maxlen){
                        maxlen = j+1-i;
                        max_str = s.substring(i, j+1);
                    }
                }
            }
        }
    return max_str;
    }
    
    public boolean isPalindrome(String s){
        for(int i=0;i<s.length()/2;i++){
            if(s.charAt(i)!=s.charAt(s.length()-i-1)){
                return false;
            }
        }
        return true;
    }
}

Optimized Solution

We could accomplish the same thing we did above by reducing one loop. We can do this by expanding the string at center and check for palindrome. This way, we optimize for not finding one, but instead to detect there's no palindrome and exit.

R E N T N O W

We will use a helper function which gets the index of two characters. It then expands to the right and left until we detect there's no palindrome.

Below is the Java implementation,

class Solution {
    public String longestPalindrome(String s) {
      if(s==null || s.length()==0) return "";
      int start = 0, end = 0;
      int len1 = 0, len2 = 0;
      for(int i=0;i<s.length();i++){
          len1 = expandStringAtCenter(s, i, i);
          len2 = expandStringAtCenter(s, i, i+1);
          int len = Math.max(len1, len2);
          if(len > end-start){
              start = i -(len-1)/2;
              end = i+len/2;
          }
      } 
        return s.substring(start, end+1);
    }
    
    public int expandStringAtCenter(String s, int left, int right){
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R-L-1;
    }
}

The time complexity for longest palindromic substring is now O(n^2).