Longest Palindromic Substring

Longest Palindromic Substring: 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"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public String longestPalindrome(String s) {
    int n = s.length();
    if(n == 1) return s;

    boolean[] dp = new boolean[n];
    int maxLength = 0, start = -1, end = -1;

    for(int i = n - 1; i >= 0; --i){
        for(int j = n - 1; j >= i; --j){
            if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[j-1])){
                dp[j] = true;
                if((start == -1 && end == -1) || (j-i+1 > maxLength)){
                    start = i;
                    end = j;
                    maxLength = j - i + 1;
                }
            }else{
                dp[j] = false;
            }
        }
    }

    if(start == -1) return s.substring(0, 1);
    return s.substring(start, end+1);
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length;
  if (n === 1) return s;

  const dp = new Array(n).fill(false);
  let maxLength = 0;
  let start = -1;
  let end = -1;

  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j >= i; j--) {
      if (s[i] === s[j] && (j - i <= 2 || dp[j - 1])) {
        dp[j] = true;
        if ((start === -1 && end === -1) || j - i + 1 > maxLength) {
          start = i;
          end = j;
          maxLength = j - i + 1;
        }
      } else {
        dp[j] = false;
      }
    }
  }

  if (start === -1) return s.substring(0, 1);
  return s.substring(start, end + 1);
};

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 1:
            return s

        dp = [False] * n
        maxLength = 0
        start = -1
        end = -1

        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                if s[i] == s[j] and (j - i <= 2 or dp[j - 1]):
                    dp[j] = True
                    if start == -1 and end == -1 or j - i + 1 > maxLength:
                        start = i
                        end = j
                        maxLength = j - i + 1
                else:
                    dp[j] = False

        if start == -1:
            return s[0]
        return s[start: end + 1]

class Solution {
public:
    string longestPalindrome(string s) {
        const int n = s.length();
        if (n == 1) return s;

        vector<bool> dp(n, false);
        int maxLength = 0;
        int start = -1;
        int end = -1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (s[i] == s[j] && (j - i <= 2 || dp[j - 1])) {
                    dp[j] = true;
                    if ((start == -1 && end == -1) || (j - i + 1 > maxLength)) {
                        start = i;
                        end = j;
                        maxLength = j - i + 1;
                    }
                } else {
                    dp[j] = false;
                }
            }
        }

        if (start == -1) return s.substr(0, 1);
        return s.substr(start, end - start + 1);
    }
};

Time/Space Complexity:

Time Complexity: O(n^2)
Space Complexity: O(n)

Explanation:

First thing to think about when you have a string as input and your goal is to find maximum subsequence or substring it's how you can solve it with the dp approach. Usually we would form a matrix (n*n) of the string, so both rows and columns match a character in string. If you have two strings you want to compare then you would have matrix s1.length() x s2.length(). Let's say we have a matrix where each row represents a character in the input string which is the first character of some substring (e.g. row = 0 we begin with s.charAt(0), for row = 1 it would be s.charAt(1) and so on). And let's define columns such that character at specific columns represents last character of our substring, that would lead us to dp[i][j] (some value/state we're tracking) for substring of the original string starting at i and ending at j. Let's define the value at dp[i][j] as information that s.substring(i,j+1) is a palindrome (in java end of substring method is not inclusive, so we have to do j+1 to include j as last character). First note that any single character is palindrome on its own (e.g. a reads the same from left and right), so the diagonal of our matrix represents single character substrings starting and ending at the same character, so the dp[i][j] iff i == j will be true. So that's the base case, but if we have substring with more characters how do we know if it's a palindrome? Well substring starting at i and ending at j is a palindrome if first and last character are equal and if one of the following requirements is satisfied:

there is only one character between i and j, so the total length of the string is 3 (e.g. aba)
substring starting at i+1 and ending at j-1 is also palindrome (e.g. ababa)

So, if we first check if bab is palindrome we can than check ababa, so we start from the end of the string:

Java
JavaScript
Python
C++

public String longestPalindrome(String s) {
    int n = s.length();
    if(n == 1) return s;

    boolean[][] dp = new boolean[n][n];
    int maxLength = 0, start = -1, end = -1;

    for(int i = 0; i < n; ++i){
        dp[i][i] = true;
    }

    for(int i = n - 1; i >= 0; --i){
        for(int j = n - 1; j > i; --j){
            if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i+1][j-1])){
                dp[i][j] = true;
                if((start == -1 && end == -1) || (j-i+1 > maxLength)){
                    start = i;
                    end = j;
                    maxLength = j - i + 1;
                }
            }
        }
    }

    if(start == -1) return s.substring(0, 1);
    return s.substring(start, end+1);
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length;
  if (n === 1) return s;

  const dp = Array.from(Array(n), () => Array(n).fill(false));
  let maxLength = 0;
  let start = -1;
  let end = -1;

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j > i; j--) {
      if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if ((start === -1 && end === -1) || j - i + 1 > maxLength) {
          start = i;
          end = j;
          maxLength = j - i + 1;
        }
      }
    }
  }

  if (start === -1) return s.substring(0, 1);
  return s.substring(start, end + 1);
};

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 1:
            return s

        dp = [[False] * n for _ in range(n)]
        maxLength = 0
        start = -1
        end = -1

        for i in range(n):
            dp[i][i] = True

        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i, -1):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if start == -1 and end == -1 or j - i + 1 > maxLength:
                        start = i
                        end = j
                        maxLength = j - i + 1

        if start == -1:
            return s[0]
        return s[start: end + 1]

class Solution {
public:
    string longestPalindrome(string s) {
        const int n = s.length();
        if (n == 1) return s;

        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int maxLength = 0;
        int start = -1;
        int end = -1;

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if ((start == -1 && end == -1) || (j - i + 1 > maxLength)) {
                        start = i;
                        end = j;
                        maxLength = j - i + 1;
                    }
                }
            }
        }

        if (start == -1) return s.substr(0, 1);
        return s.substr(start, end - start + 1);
    }
};

Our requirements are expressed in the line s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i+1][j-1]). We also track the start and the end of the longest palindrome substring and its total length, so we can return it as our result. But notice that we don't really need a matrix to hold our values, we can do it with array, since our current calculation is only dependent on the previous, we can reduce the dimensionality of our dp storage. dp[j-1] will only be true if in the last calculation substring at i+1 and ending at j-1 was a palindrome, so for our substring starting at i and ending at j to be palindrome too it's enough if the characters at index i and j are the same and if the total length of current substring is 3, or our previous calculation for substring was a palindrome (dp[j-1]=true). The final solution is given in the Solution section.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​