Longest Palindromic Substring

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case)

Expand Around Center

In fact, we could solve it in O(n2) time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−1 such centers.

You might be asking why there are 2n−1 but not nn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.

Check the following diagram to understand that how a odd length palindrome “pbabp” expands around center.

Odd Length Palindrome Expanding around Center
class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        String odd_length="";
        String even_length ="";
        String longest_palindrome ="";
        for(int i = 0 ; i < s.length() ; i++){
            odd_length = expandAroundCenter(s,i,i);
            even_length = expandAroundCenter(s,i,i+1);
            String cur_longest = odd_length.length() > even_length.length() ?
                odd_length : even_length;
            if(cur_longest.length() > longest_palindrome.length()){
                longest_palindrome = cur_longest;
            }
        }
        return longest_palindrome;
    }
    
    private String expandAroundCenter(String s, int l, int r){
        while( l >= 0 && r < s.length()){
            if(s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }else{
                break;
            }
        }
        return s.substring(l+1, r);
    }
}

Complexity Analysis

  • Time Complexity : O(n2). Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n2).
  • Space complexity : O(1).

Categories: String

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s