Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Palindromic Substring

Find the longest contiguous palindromic substring in a given string using dynamic programming and two-pointer expansion techniques efficiently.

two pointers string dynamic programming

Problem Statement

Given a string s, find and return the longest contiguous substring that reads the same forwards and backwards. Each character alone counts as a palindrome, and the solution must consider overlaps and expansions efficiently.

You may use dynamic programming to track known palindromic ranges and expand around potential centers. Constraints include string lengths up to 1000 characters, containing only digits and English letters, and the solution must maximize efficiency while correctly identifying all possible palindromic centers.

Examples

Example 1

Input: s = "babad"

Output: "bab"

"aba" is also a valid answer.

Example 2

Input: s = "cbbd"

Output: "bb"

Example details omitted.

Constraints

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

Solution Approach

Expand Around Centers with Two-Pointer Technique

For each character in the string, treat it as a potential palindrome center. Expand two pointers outward simultaneously to check if characters match. Track the longest substring found during these expansions. Handle both odd-length and even-length palindromes separately. This approach leverages the failure mode of naive checking by avoiding repeated scans and ensures that all contiguous palindromes are considered without exceeding linear time per expansion.

Dynamic Programming State Transition Table

Build a 2D table where dp[i][j] indicates whether the substring from i to j is a palindrome. Start with substrings of length 1 and 2 as base cases. For longer substrings, rely on dp[i+1][j-1] and character matches at i and j. This method reuses previously computed palindrome results, preventing redundant checks, directly reflecting the state transition dynamic programming pattern and reducing unnecessary recalculation for larger spans.

Combine Expansion and DP for Optimal Tracking

Integrate center expansion with DP knowledge by skipping indices that cannot yield longer palindromes based on previous states. Track starting index and length of the current longest palindrome, updating only when a larger palindrome is found. This hybrid approach ensures the solution leverages two-pointer checking speed while avoiding redundant expansions already verified by DP, directly addressing efficiency failure modes and keeping operations within acceptable time and space bounds.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The solution performs linear expansions around each center combined with DP lookups, resulting in O(n) time complexity. Space complexity is O(n) due to the DP table storing palindrome states, efficiently handling all substrings up to length 1000 without redundant recalculation, ensuring the algorithm scales for maximum input sizes.

What Interviewers Usually Probe

Do you identify both odd and even length palindromes during center expansion?
Can you explain how previously computed palindromes reduce redundant checks in the DP table?
Will you update the longest palindrome tracking correctly when multiple candidates of the same length exist?

Common Pitfalls or Variants

Common pitfalls

Forgetting to check even-length palindromes, which requires treating centers between characters.
Not initializing DP base cases correctly, leading to incorrect longer palindrome computation.
Expanding beyond string bounds when checking centers, causing runtime errors.

Follow-up variants

Find the number of distinct palindromic substrings in a given string.
Return the longest palindromic subsequence instead of substring, allowing non-contiguous characters.
Compute the longest palindrome in a streaming string with limited memory, requiring on-the-fly updates.

FAQ

What is the main pattern used in Longest Palindromic Substring?

The primary pattern is state transition dynamic programming, which uses previously computed palindromes to efficiently find larger ones and track expansions.

How do I handle both odd and even length palindromes?

Treat each character as a center for odd-length palindromes and each pair of adjacent characters as a center for even-length palindromes, expanding outwards from each center.

Can this approach handle strings up to 1000 characters efficiently?

Yes, by combining two-pointer expansion with DP state reuse, the solution maintains O(n) time and O(n) space complexity, making it efficient for maximum constraints.

What are common mistakes when implementing this problem?

Common pitfalls include forgetting even-length palindromes, misinitializing DP base cases, and expanding pointers beyond string boundaries causing errors.

How does the DP state transition work here?

The DP table tracks whether substring s[i..j] is a palindrome using dp[i+1][j-1] and character matches, allowing previously found palindromes to inform longer substring checks efficiently.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent whether the string $s[i..j]$ is a palindrome, initially $f[i][j] = true$.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[True] * n for _ in range(n)]
        k, mx = 0, 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = False
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                    if f[i][j] and mx < j - i + 1:
                        k, mx = i, j - i + 1
        return s[k : k + mx]

Solution 2: Enumerate Palindrome Midpoint

We can enumerate the midpoint of the palindrome, spread to both sides, and find the longest palindrome.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[True] * n for _ in range(n)]
        k, mx = 0, 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = False
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                    if f[i][j] and mx < j - i + 1:
                        k, mx = i, j - i + 1
        return s[k : k + mx]

Continue Practicing

#647 palindromic substrings #22 generate parentheses #32 longest valid parentheses