Leetcode — 5. Longest Palindromic Substring

The link to the problem: https://leetcode.com/problems/longest-palindromic-substring/

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

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

Thoughts:

The definition of a palindrome is a word that reads the same backward as forward. Hence, there are two different ways how we determine a string is a palindrome. We need two pointers i and j that helps us pointing different positions at the same time in these two different methods:

🔧 Method 1. We can set pointer i at the beginning of the word, and j at the end of the word. Both the pointer i and the pointer j are heading to the middle point of the word. Hence, if the word is a palindrome, the character that i is pointing at and the character that j is pointing at must be the same till these two pointers meet in the middle of the word.

🔧 Method 2. We can set pointer i and pointer j in the middle of the word. We will let i head to the beginning of the word (i.e., head to the left), and let j head to the end of the word (head to the right). If the word is a palindrome, the character that i is pointing at and the character that j is pointing at must be the same till both of them reaches the head/tail at the same time.

Of course, you can check all the possible substrings in the whole string. Hence, what we are going to do is keep forming substrings of a certain length. We will form a substring from the longest to the shortest length and use a helper method to check whether it is a palindrome. We can just return the first palindrome substring we found since the first palindrome substring we found will also be the longest substring in the whole string.

⚠️Note that we can either implement method 1 or method 2 in our helper method since their time complexities are the same.

Below is the 496ms code that beats 10% —

public String longestPalindrome(String s) {
        int n = s.length();
        if(n<=1)
            return s;
        for(int len=n;len>=2;len--)
        {
            for(int left=0;left+len<=n;left++)
            {
                int right = left+len-1;
                if(isPal(s,left,right))
                    return s.substring(left, right+1);
            }
        }
        return s.substring(0,1);
    }
    public boolean isPal(String s, int l,int r){
        while(l<r)
        {
            if(s.charAt(l++)!=s.charAt(r--))
                return false;
        }
        return true;
    }

Since we will actually redundantly check if the same range of a substring is a palindrome, we can store all the results of the ranges we have checked into a 2D array. We will use dp[i][j] to represent if the substring that starts from index i to index j is a palindrome. i.e., dp[0][2] represents if “abc” is palindrome when s = “abcde”.

Hence, we are going to implement the idea of method 2 that we mentioned above to find our palindrome substrings. This time, we will form the smaller lengths of the substrings first and store the result of whether they are palindrome or not in the 2D array. Hence, we only need to check if the leftmost character and the rightmost character of the current substring is the same, if yes, then whether the current substring is a palindrome will depend on whether “its inner substring” is a palindrome!

For example, assume we know that “acbca” is a palindrome. If we want to know whether “xacbcax” is a palindrome, we just need to compare the first character and the last character, if they are the same character, then we can also assume “xacbcax” is a palindrome.

Below is the 193ms code that beats 20% —

public String longestPalindrome(String s) {
        int n = s.length();
        if(n<=1)
            return s;
        String rst = s.substring(0,1);
        boolean[][] dp = new boolean[n][n];
        for(int len=1;len<=n;len++)
        {
            for(int left=0;left+len<=n;left++)
            {
                int right = left+len-1;
                if(s.charAt(left)!=s.charAt(right))
                    continue;
                if(right-left<=2)//like "a" "aa" "aba"
                    dp[left][right] = true;
                else
                    dp[left][right] = dp[left+1][right-1];
                int curLen = rst.length();
                if(dp[left][right] && curLen < len)
                    rst = s.substring(left,right+1);
            }
        }
        return rst;
    }

However, the time complexity is still high since we are checking mostly all the possible substring in the whole string.

Code Logic:

In this problem, you don’t need to really return all the palindrome substrings that have the longest length. Hence, you can just return any valid palindrome substring as long as it is one of the longest palindrome substrings.

This time, instead of guessing the starting point and the ending point of our substring, we are going to guess the midpoint of the substring.

There are two types of palindrome — odd number length and even number length. Hence, we will either have one midpoint or two midpoints.

Since every position of the characters can be the midpoint of our longest substring, we are going to use a for-loop to keep trying. We will use a helper method and pass our “left pointer” and “right pointer”, using the idea of method 2, which we mentioned at the very beginning of this story.

We will call the helper method twice at every possible midpoint. It is because we don’t know whether the length of the palindrome we are going to form is an odd number or an even number.

For example, for input = "abcde". 
If we are at position 1, where 'b' is at, then the longest substring that 'b' is in the middle will be "abc" and "abcd".

Below is the 26ms code that beats 63%—

    public String longestPalindrome(String s) {
        String rst = "";
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            //i is the mid point of the substr
            String cur = helper(s, i-1, i+1);
            if(cur.length()>rst.length())
                rst = cur;
            cur = helper(s, i, i+1);
            if(cur.length()>rst.length())
                rst = cur;
        }
        return rst;
    }
    public String helper(String s, int left,int right){
        int n = s.length();
        while(left>=0 && right<n 
              && s.charAt(left) == s.charAt(right))
        {
            left--;
            right++;
        }
        //here: s[left] != s[right]
        return s.substring(left+1, right);
    }

Since i represents the midpoint of the “possible palindrome substring”, the longest length of this palindrome substring is either twice of i to the first character or i to the last character of the whole string depends on which i is closer to. (For example, if i = 1 in “abcdef”, then the longest substring when i is in the middle point will be “abcd”.)

Hence, we can even skip calling the helper method if we found the current i is impossible to form a longer palindrome than the current string.

Below is the 17ms code that beats 94.6% —

public String longestPalindrome(String s) {
        String rst = "";
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            int longest = Math.min(i, n-i+1);
            if(rst.length() > longest*2)
                return rst;
            //i is the mid point of the substr
            String cur = helper(s, i-1, i+1);
            if(cur.length()>rst.length())
                rst = cur;
            cur = helper(s, i, i+1);
            if(cur.length()>rst.length())
                rst = cur;
        }
        return rst;
    }
    public String helper(String s, int left,int right){
        int n = s.length();
        while(left>=0 && right<n 
              && s.charAt(left) == s.charAt(right))
        {
            left--;
            right++;
        }
        //here: s[left] != s[right]
        return s.substring(left+1, right);
    }