Longest Palindromic Substring

medium
Dynamic ProgrammingStringDynamic Programming

Given a string s, return the longest palindromic substring in s. A palindrome reads the same forwards and backwards. If there are multiple answers of the same length, return any one of them.

Examples

Example 1

  • Input: s = "babad"
  • Output: "bab"
  • Explanation: "aba" is also a valid answer since both are palindromes of length 3.

Example 2

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

Example 3

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

Constraints

  • 1 <= s.length <= 1000
  • s consists of only lowercase English letters.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Expand Around Center

Intuition

Every palindrome has a center — either a single character (odd length) or a pair of adjacent characters (even length). We can find the longest palindrome by trying each possible center and expanding outward as long as the characters on both sides match. This gives us at most 2n - 1 centers to check (n for odd-length, n-1 for even-length palindromes), and each expansion takes O(n) time in the worst case.

Algorithm

  1. Initialize variables to track the start index and maximum length of the longest palindrome found.
  2. For each index `i` in the string, expand around center for both odd-length (`left = i, right = i`) and even-length (`left = i, right = i + 1`) palindromes.
  3. For each center, expand outward while `left >= 0`, `right < n`, and `s[left] == s[right]`.
  4. After expansion, if the palindrome length is greater than the current maximum, update the start index and maximum length.
  5. Return the substring from start to start + maxLength.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;

        int start = 0, maxLen = 1;

        auto expand = [&](int left, int right) {
            while (left >= 0 && right < n && s[left] == s[right]) {
                if (right - left + 1 > maxLen) {
                    start = left;
                    maxLen = right - left + 1;
                }
                left--;
                right++;
            }
        };

        for (int i = 0; i < n; i++) {
            expand(i, i);
            expand(i, i + 1);
        }

        return s.substr(start, maxLen);
    }
};
Java 21
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        int start = 0, maxLen = 1;

        for (int i = 0; i < n; i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }

        return s.substring(start, start + maxLen);
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}
Python 3.12
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        start, max_len = 0, 1

        def expand(left: int, right: int) -> None:
            nonlocal start, max_len
            while left >= 0 and right < n and s[left] == s[right]:
                if right - left + 1 > max_len:
                    start = left
                    max_len = right - left + 1
                left -= 1
                right += 1

        for i in range(n):
            expand(i, i)
            expand(i, i + 1)

        return s[start:start + max_len]
Go 1.26
func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    start, maxLen := 0, 1

    expand := func(left, right int) {
        for left >= 0 && right < n && s[left] == s[right] {
            if right-left+1 > maxLen {
                start = left
                maxLen = right - left + 1
            }
            left--
            right++
        }
    }

    for i := 0; i < n; i++ {
        expand(i, i)
        expand(i, i+1)
    }

    return s[start : start+maxLen]
}
Approach 2

Dynamic Programming

Intuition

We can use a 2D boolean table where dp[i][j] is true if the substring s[i..j] is a palindrome. A substring is a palindrome if the first and last characters match and the inner substring is also a palindrome. We fill the table for increasing substring lengths, building on previously computed shorter palindromes. We track the longest palindrome found during the process.

Algorithm

  1. Create a 2D boolean array `dp` of size `n x n`, initialized to false.
  2. Mark all single characters as palindromes: `dp[i][i] = true`.
  3. Check all substrings of length 2: `dp[i][i+1] = (s[i] == s[i+1])`.
  4. For lengths 3 to n, set `dp[i][j] = true` if `s[i] == s[j]` and `dp[i+1][j-1]` is true.
  5. Track the start index and length of the longest palindrome found.
  6. Return the longest palindromic substring.
TimeO(n^2)SpaceO(n^2)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;

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

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

        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }

        return s.substr(start, maxLen);
    }
};
Java 21
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;

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

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}
Python 3.12
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        dp = [[False] * n for _ in range(n)]
        start, max_len = 0, 1

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

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2

        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    start = i
                    max_len = length

        return s[start:start + max_len]
Go 1.26
func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    start, maxLen := 0, 1

    for i := 0; i < n-1; i++ {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            start = i
            maxLen = 2
        }
    }

    for length := 3; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                start = i
                maxLen = length
            }
        }
    }

    return s[start : start+maxLen]
}

Frequently asked questions

What is the optimal time complexity of Longest Palindromic Substring?

The most efficient approach in this guide ("Dynamic Programming") runs in O(n^2) time and uses O(n^2) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Longest Palindromic Substring use?

Longest Palindromic Substring is a medium-level Dynamic Programming problem involving String, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Palindromic Substring be solved without extra space?

The most space-efficient approach in this guide uses O(n^2) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n^2).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Palindromic Substrings

Original problem: leetcode.com

Loading editor...
Input
s=
"cbbd"
Expected Output
"bb"