Leetcode - 5. Longest Palindromic Substring ( Tutorial + Solution in C )

=>Try Yourself First. For help Scroll Down.

Problem Link: https://leetcode.com/problems/longest-palindromic-substring/

Problem Clearance: In this problem, you will be given a string. You have to find out the maximum length of a palindromic substring from the given string. A string is a palindrome if it remains the same when reversed. 

For example, you are given "abacabc". Here we have 10 palindromic substrings. They are - { "a", "b", "a", "c", "a", "b", "c", "aba", "bacab", "aca" }. You have to return "bacab" as it is the longest among palindromic substrings. 

Required Knowledge: Looping, palindrome checking.

Tutorial: I will share the way I approached the problem and formulated the problem to pass the time limit. I will start with a very naive approach. Then I will lower down the complexity by improving the approach. 

Approach 1: Starting from ith index we will check for the longest palindrome that we encounter while traversing. The pseudo-code of the naive approach will be something like this - 

// |A| = Length of string A

R = NULL;
function (S)
  for i in range(|S|):
    for j=i to range(|S|):
      if S[i....j] is palidrome and |S[i....j]| is greater than |R|:
         assign S[i...j] to R
return R

If the length of the string is N. The complexity of the previous approach will be O(N³) approximately. As the length of the string could be N it will take almost 10⁹ operations at most which will surely not pass. It will result in Time Limit Exceeded.

Approach 2: Can we improve the previous approach? 

Yes!! In line 6 of the previous code, instead of taking j for the entire length of string, we will consider checking the strings of lengths more than (S[i....j]) every single j. The number of palindrome checking operations will be reduced. The overall complexity will be slightly higher than O(N²) in the worst case.

// |A| = length of string A

R = NULL;
function (S)
  for i in range(|S|):
    for j=i+|R| to range(|S|):
      if S[i....j] is palidrome and |S[i....j]| is greater than |R|:
         R = S;
return R

Approach 3: Can we further improve our approach? 

Yes. We can. Instead of taking the i^th index as the start of a string, we can consider the i^th index as the mid-point of a string. From the i^th index, we can go back and forth once at a time to check whether we encounter the same character of the string. This is approach can figure out the longest palindrome from the given with straight O(N²) complexity. 

A problem you might encounter is test cases with even length palindrome string. Take good care of moving the backward iterator. 

That's all. Hope you understand the concept. You can see the implementation of the third approach below if you want to.

Code: 

int mstrlen(char *s){
    int i = 0;
    for(;s[i];i++);
    return i;
}

char * longestPalindrome(char * s){
    int len = mstrlen(s);
    int mxl = 1, mi = 0, mj = 0;
    for(int i=0; i<len; i++){
        for(int j=0; i-j>=0 && i+j<len; j++){
            if(s[i-j] != s[i+j] ){
                break;
            }
            else if(mxl < 2*j + 1){
                mxl = 2*j + 1;
                mi = i - j, mj = i+j;
            }
        }
        
        for(int j=1; i-j+1>=0 && i+j<len; j++){
            if(s[i-j+1]!= s[i+j]){
                break;
            }
            else if(mxl < 2*j){
                mxl = 2*j;
                mi = i-j+1, mj = i+j;
            }
        }
    }
    //printf("Length %d\n", mxl);
    char * res; res = (char *)malloc(sizeof(char) * len+5);
    for(int i=mi; i<=mj; i++){
        res[i-mi] = s[i];
    }
    res[mxl] = '\0';
    return res;
}

=> Leave a comment if you have anything to share. Thank you.