Approach Summary
Expand around each center. Track the longest expansion found. Returns the actual substring, not just the length.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 2D Dynamic Programming Tabulation | O(n^2) | O(n^2) | dp[i][j] is true if substring s[i...j] is a palindrome, checking dp[i+1][j-1] for lengths >= 3. |
| 2 Approach 2: Expand Around Center (Optimal) | O(n^2) | O(1) | Expand outward from 2n - 1 centers (single characters and pairs) in O(1) auxiliary space. |
Step 1: Baseline
Approach 1: 2D Dynamic Programming Tabulation
Time: O(n^2)
Space: O(n^2)
Create a 2D boolean array dp[n][n]. All single characters dp[i][i] are palindromes. For pairs dp[i][i+1], check if s[i] == s[i+1]. For substrings of length 3 to n, s[i...j] is a palindrome if s[i] == s[j] and the inner substring dp[i+1][j-1] is also a palindrome.
Approach 1: 2D Dynamic Programming Tabulation Implementation
Approach 1: 2D Dynamic Programming Tabulation
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n <= 1) 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);
}
}class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n <= 1) 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);
}
};class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n <= 1:
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, max_len = i, 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, max_len = i, length
return s[start:start + max_len]function longestPalindrome(s) {
const n = s.length;
if (n <= 1) return s;
const dp = Array.from({ length: n }, () => new Array(n).fill(false));
let start = 0, maxLen = 1;
for (let i = 0; i < n; i++) dp[i][i] = true;
for (let i = 0; i < n - 1; i++) {
if (s[i] === s[i + 1]) {
dp[i][i + 1] = true;
start = i;
maxLen = 2;
}
}
for (let len = 3; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
maxLen = len;
}
}
}
return s.substring(start, start + maxLen);
} Step 2: Most Optimized
Approach 2: Expand Around Center (Optimal)
Time: O(n^2)
Space: O(1)
A palindrome mirrors around its center. A string of length n has 2n - 1 potential centers (n single-character centers and n - 1 character-pair centers). For each center, expand left and right as long as s[left] == s[right] and indices remain within bounds. Track the longest window found.
Approach 2: Expand Around Center (Optimal) Implementation
Approach 2: Expand Around Center (Optimal)
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int currMax = 0;
String currMaxString = "";
for (int i = 0; i < n; i++) {
int left = i, right = i;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
if (right - left + 1 > currMax) {
currMax = right - left + 1;
currMaxString = s.substring(left, right + 1);
}
left--; right++;
}
left = i; right = i + 1;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
if (right - left + 1 > currMax) {
currMax = right - left + 1;
currMaxString = s.substring(left, right + 1);
}
left--; right++;
}
}
return currMaxString;
}
}class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int currMax = 0;
string currMaxString = "";
for (int i = 0; i < n; i++) {
int left = i, right = i;
while (left >= 0 && right < n && s[left] == s[right]) {
if (right - left + 1 > currMax) {
currMax = right - left + 1;
currMaxString = s.substr(left, right - left + 1);
}
left--; right++;
}
left = i; right = i + 1;
while (left >= 0 && right < n && s[left] == s[right]) {
if (right - left + 1 > currMax) {
currMax = right - left + 1;
currMaxString = s.substr(left, right - left + 1);
}
left--; right++;
}
}
return currMaxString;
}
};class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
curr_max = 0
res = ""
for i in range(n):
# odd length
l, r = i, i
while l >= 0 and r < n and s[l] == s[r]:
if r - l + 1 > curr_max:
curr_max = r - l + 1
res = s[l:r + 1]
l -= 1
r += 1
# even length
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
if r - l + 1 > curr_max:
curr_max = r - l + 1
res = s[l:r + 1]
l -= 1
r += 1
return resfunction longestPalindrome(s) {
let currMax = 0, res = "";
const n = s.length;
for (let i = 0; i < n; i++) {
let l = i, r = i;
while (l >= 0 && r < n && s[l] === s[r]) {
if (r - l + 1 > currMax) {
currMax = r - l + 1;
res = s.substring(l, r + 1);
}
l--; r++;
}
l = i; r = i + 1;
while (l >= 0 && r < n && s[l] === s[r]) {
if (r - l + 1 > currMax) {
currMax = r - l + 1;
res = s.substring(l, r + 1);
}
l--; r++;
}
}
return res;
}Edge Cases to Watch
- Single character string (e.g. "a"; returns "a")
- String with no multi-character palindrome (e.g. "abc"; returns any single character)
- Entire string is a palindrome (e.g. "racecar"; returns full string)
- Even length palindrome (e.g. "cbbd"; returns "bb")
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- "Find the longest palindrome"
- Expand-around-center beats O(n²) DP space-wise
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(1)
Tags
String Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for Longest Palindromic Substring?
The optimal solution for Longest Palindromic Substring achieves O(n²) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n^2) because there are 2n - 1 possible centers, and expanding outward from each takes at most O(n) steps. Space complexity is O(1) auxiliary space since expansions only update coordinate pointers.
How do I identify that Longest Palindromic Substring requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: "Find the longest palindrome"; Expand-around-center beats O(n²) DP space-wise. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Longest Palindromic Substring?
Essential edge cases to verify include: Single character string (e.g. "a"; returns "a"); String with no multi-character palindrome (e.g. "abc"; returns any single character); Entire string is a palindrome (e.g. "racecar"; returns full string); Even length palindrome (e.g. "cbbd"; returns "bb"). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Palindromic Substring?
Longest Palindromic Substring is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google, Facebook.