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)
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.
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:
Comments
Post a Comment