Leetcode 5: Longest Palindromic Substring

 

1. Problem Statement (Simple Explanation):

You are given a string s.

You need to return the longest substring of s that is a palindrome.

• A palindrome is a string that reads the same forwards and backwards.

• A substring is a contiguous part of the string.

You can return any one longest palindromic substring if there are multiple answers.

2. Examples:

Example 1

Input: s = "babad"

Output: "bab"

Explanation:

• Palindromic substrings include "bab", "aba", "b", "a", "d", etc.

• "bab" and "aba" both have length 3.

• You can return either "bab" or "aba".

Example 2

Input: s = "cbbd"

Output: "bb"

Explanation:

• Palindromic substrings: "c", "b", "bb", "d".

• Longest is "bb" (length 2).

Constraints

• 1≤∣s∣≤1000

• s consists only of digits and English letters.

3. Approach 1 – Brute Force (Check All Substrings):

Intuition

• Generate all substrings of s.

• For each substring, check if it is a palindrome.

• Track the longest palindromic substring.

This is straightforward but too slow for ∣s∣=1000.

Algorithm (High Level)

1. For every pair (i, j) with 0 <= i <= j < n:

• Consider substring s[i..j].

• Check if s[i..j] is a palindrome by comparing characters from both ends.

• If palindromic and longer than current best, update the answer.

Pseudo-code (Brute Force)

Complexity

• Checking all substrings: O(n2) substrings.

• Each palindrome check: O(n) worst case.

• Total time: O(n3)

• Space: O(1)

Good for understanding, but too slow.

4. Approach 2 – Expand Around Center (O(n²), Practical and Common):

This is the standard interview solution.

Intuition

A palindrome is symmetric around its center.

• For odd-length palindromes: a single center character, e.g., "aba" centered at 'b'.

• For even-length palindromes: center is between two characters, e.g., "abba" centered between the two 'b's.

For each index or gap in s, we:

• Expand outwards (left--, right++) while characters are equal.

• Track the longest palindrome found.

There are 2n - 1 possible centers:

• n odd centers at each character.

• n - 1 even centers between characters.

Helper: Expand from the Center

Given a center (left, right), expand while s[left] == s[right] and inside bounds.

Return the length of the palindrome.

Pseudo-code (Expand Around Center)

Complexity

• For each of the n positions, we expand in O(n) worst case.

• Total time: O(n2)

• Extra space: O(1)

For n <= 1000, this is fast enough and is the typical accepted solution.

5. Approach 3 – Dynamic Programming (O(n²) Time, O(n²) Space):

Idea

Use a 2D boolean DP table dp[i][j]:

• dp[i][j] = true if substring s[i..j] is a palindrome.

Recurrence:

• Single char always palindrome:

• dp[i][i] = true

• Two chars:

• dp[i][i+1] = (s[i] == s[i+1])

• More than two chars:

• dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

Then iterate substrings by length and track the longest palindromic substring.

But this uses O(n2) space, and center-expansion is usually preferred.

6. Java code:

7. C code:

8. C++ code:

9. Python code:

10. JavaScript code:

<<<PREV

NEXT>>>