LeetCode 5. Longest Palindromic Substring



Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"


A palindromic string meets two criteria:

  1. first and the last character are the same
  2. the inner word between the first and the last character is a palindromic string

The basic idea is to use dynamic programming to determine whether a substring is palindromic string base on above criteria.

Need to be careful that when returning the result, the end index need to plus 1, because java substring method doesn’t include the ending index.

Java Solution

class Solution {
    public String longestPalindrome(String s) {        
        if (s == null || s.length() < 2) {
            return s;

        int length = s.length();
        boolean[][] isPalindrome = new boolean[length][length];
        int left = 0;
        int right = 0;
        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j; i++) {
                boolean isInnerWordPalindrome = isPalindrome[i + 1][j - 1] || j - i <= 2;
                if (s.charAt(i) == s.charAt(j) && isInnerWordPalindrome) {
                    isPalindrome[i][j] = true;
                    if (j - i > right - left) {
                        left = i;
                        right = j;
        return s.substring(left, right + 1);
        // Time Complexity: O(n ^ 2)
        // Space Complexity: O(n ^ 2)

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:        
        if not s:
            return ""
        longest = ""
        for middle in range(len(s)):
            sub = self.find_palindrome_from(s, middle, middle)
            if len(sub) > len(longest):
                longest = sub
            sub = self.find_palindrome_from(s, middle, middle + 1)
            if len(sub) > len(longest):
                longest = sub
        return longest
    def find_palindrome_from(self, string, left, right):
        while left >= 0 and right < len(string):
            if string[left] != string[right]:
            left -= 1
            right += 1
        return string[left + 1:right]        
  • Time complexity: O(N^2).
  • Space complexity: O(S).

6 Thoughts to “LeetCode 5. Longest Palindromic Substring”

  1. It’s interesting how you do the double for loop
    The way how you set up right now is “i” will never exceed “j” and “i” is the inner loop

    let me rename “i” and “j” for clarity sake i = left and j = right
    the way how you set up after renaming looks like this

    for (right = 1; right < length; right ++) {
    for (left = 0; left < right; left ++) {
    * …. *

    just curious why?
    vs something like this

    for (left = 0; left < length – 1; left++ ) {
    for (right = (left + 1); right < length; right ++ ) {
    * …. *

    Correct me if I am wrong, I print out substring with i, j index and I think both of them are the same.
    In my opinion the second for-loop feels more intuitive unless this will cause an issue building out the "isInnerWordPalindrome" matrix


  2. I have the same question in python but the platform accepts input only in this format. The problem is Test Case with 12 as length and abcbcabbacba as string is resulting in 12 and same string as output , it should be 8, bcabbacb. Can you tell where I misunderstood the logic and syntax. My code is as follows:

    #input length, string

    if w == ” or len(w)<=2:

    if N<=5000:
    isPallindrome = [[0]*N]*N

    for j in range(1,N):
    for i in range(0,j):
    isInnerWordPallindrome = isPallindrome[i+1][j-1] or j-i right-left:
    left = i
    right = j

    var1 = len(w[left:right+1])
    var2 = w[left:right+1]

    Thank you in advance!

  3. Can you please explain why are you taking j from 1 to length and not from 0 to length inside the first loop?
    Please elaborate both the ranges for i and j.

    Thanks in advance.

    1. Try thinking about it simply, i is the left index and j is the right index of a word.
      In order to get at least one character of a word, j has been to at least one index after i. If i’s index is 0, then j’s index would be 1.
      For i, its value could start from 0 to j – 1.
      For j, its value could start from 1 to the last character index of the input string (s.length() – 1).

Leave a Reply

Your email address will not be published. Required fields are marked *