Find the Longest Palindromic Substring

LeetCode question : https://leetcode.com/problems/longest-palindromic-substring/

Solution :

1. Iterative approach
2. Dynamic Programming

Question Explanation :

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Iterative Approach :

// Online Java Compiler
// Use this editor to write, compile and run your Java code online
class PalindromicString {
    
    static int start, maxLength;
    
    public static void main(String[] args) {
        System.out.println(longestPalindrome("GEEG"));
    }
    
    public static String longestPalindrome(String s) {
     int len = s.length();
     if (len < 2)
      return s;
     
        for (int i = 0; i < len-1; i++) {
          calculatePalindrome(s, i, i);   //to find palindrome when str.length() = odd
          calculatePalindrome(s, i, i+1); //to find palindrome when str.length() = even
        }
        return s.substring(start, start + maxLength);
    }
static void calculatePalindrome(String s, int j, int k) {
 while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
  j--;
  k++;
 }
 if (maxLength < k - j - 1) {
  start = j + 1;
  maxLength = k - j - 1;
 }
   }
}

Output : “GEEG”

Time Complexity : 0(n*n)

Explanation :

There is just one for loop which is self explanatory. We just run the loop n times, which is the length of String. The below piece of code needs explanation.

calculatePalindrome(s, i, i);   //to find palindrome when str.length() = odd
          calculatePalindrome(s, i, i+1); //to find palindrome when str.length() = even

We call the calculatePalindrome(s,i,i) for the strings whose length is odd like for inputs “GEEGK”, “Hello”, “GEEEG”, “GEGEGEG”.

Inside calculatePalindrome method we find out the longest palindromic String.

We call calculatePalindrome(s,i,i+1) for the strings whose length is even like for inputs “GEEG”, “GEEK ”.

Why do we call calculatePalindrome method for even and odd strings ?

Let’s take an example of an odd length string ‘GEEEG’ :

Say for example we are at index 2. We call

calculatePalindrome(string,i,i);
calculatePalindrome("GEEEG",2,2);

So i = j = 2 inside calculatePalindrome method. We check if string.charAt(i) == string.charAt(j); which is true so we decrease i and increase j. Now, i =1 and j = 3

We check again if string.charAt(1) == string.charAt(3) which is true, so we decrease i and increase j. Again we check string.charAt(0) == string.charAt(4), which is true. So the longest palindromic string is ‘GEEEG’.

The same logic of

calculatePalindrome(string,i,i);

is not possible for even length String . Example below :

Input : ‘GEEG’

Let’s consider i = 1 i.e.

calculatePalindrome("GEEG",1,1);

When we are at i = 1 and j = 1 we check string.charAt(i) == string.charAt(j) which is true so we increase j and decrease i. Now i = 0 and j=2. We again check string.charAt(i) == string.charAt(j), in this case this is false.
In this case we would never be able to compare string.charAt(0) and string.charAt(3). Hence we will use the below method to find the longest palnidromic String for inputs where length = even i.e.

calculatePalindrome(string,i,i+1);

Example :

calculatePalindrome("GEEG",1,2);

We compare string.charAt(i) == string.charAt(j) i.e string.charAt(1) == string.charAt(2) , which is true so we increase j and decrease i. Now i=0 and j = 3. Again, we compare string.charAt(0) == string.charAt(3), which is true. In this case we were able to compare string.charAt(0) == string.charAt(3). Hence we use separate method calls calculatePalindrome for even and odd strings.

Dynamic Programming Solution :

public class LongestPalinSubstring {
    // A utility function to print
    // a substring str[low,high]
    static void printSubStr(
        String str, int low, int high)
    {
        System.out.println(
            str.substring(
                low, high + 1));
    }
 
    // This function prints the longest
    // palindrome substring of str[].
    // It also returns the length of the
    // longest palindrome
    static int longestPalSubstr(String str)
    {
        // get length of input string
        int n = str.length();
 
        // table[i][j] will be false if
        // substring str[i..j] is not palindrome.
        // Else table[i][j] will be true
        boolean table[][] = new boolean[n][n];
 
        // All substrings of length 1 are palindromes
        int maxLength = 1;
        for (int i = 0; i < n; i++)
            table[i][i] = true;
 
        // check for sub-string of length 2.
        int start = 0;
        for (int i = 0; i < n - 1; i++) {
            if (str.charAt(i) == str.charAt(i + 1)) {
                table[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
 
        // Check for lengths greater than 2.
        // k is length of substring
        for (int k = 3; k <= n; ++k) {
 
            // Fix the starting index
            for (int i = 0; i < n - k + 1; i++) {
                // Get the ending index of substring from
                // starting index i and length k
               
                int j = i + k - 1;
 
                // checking for sub-string from ith index to
                // jth index if str.charAt(i+1) to
                // str.charAt(j-1) is a palindrome
                if (table[i + 1][j - 1]
                    && str.charAt(i) == str.charAt(j)) {
                    table[i][j] = true;
                    if (k > maxLength) {
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }
        System.out.print("Longest palindrome substring is; ");
        printSubStr(str, start,
                    start + maxLength - 1);
 
        // return length of LPS
        return maxLength;
    }
 
    public static void main(String[] args)
    {
 
        String str = "geeg";
        System.out.println("Length is: " + longestPalSubstr(str));
    }
}

Explanation :

Let’s take an example of ‘geeg’

There are three outer for loops used in the above program. 1st for loop is to compare the elements with itself, because all the characters in itself when checked individually is a palindrome.
‘g’,’e’,’e’,’g’ are all palindromic characters.

Next we will check the string based on a combination of 2 characters. Combination means the order of character is important. Hence we will check for ‘ge’, ‘ee’, ‘eg’.
We are not checking for the combination ‘gg’, since it can never be a palindromic string as the string is formed by 1st and last index which is not ordered.

The 3rd (last) outer loop has an inner loop too. We will check for all the combination of the input string where the number of characters in the string is >2. So for the string ‘geeg’, these would be the combination for which this for loop would run -

‘gee’

‘eeg’

‘geeg’

The outer loop would run twice for k= 3 and 4 since the input string is “GEEG”. The inner loop runs twice for k= 3 and runs once for k = 4.

Time Complexity : 0(n*n)

Conclusion

Hope this blog post was helpful. I struggled to find the iterative approach for this leetcode question. Hence thought of writing one myself. You can reach me at LinkedIn or vivek.sinless@gmail.com

Happy Learning! Cheers.