Log inSign up
mediumleetcodeNot Started

Longest Palindromic Substring

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given a string s, return *the longest palindromic substring* in s.

Example 1 · Example:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2 · Example:

Input: s = "cbbd"
Output: "bb"
Explanation: "bb" is the longest palindromic substring.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2N - 1 center expansion technique.
  • Formulate palindrome substring queries with O(1) auxiliary space.
  • Understand the core premise of Manacher's linear palindrome algorithm.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the longest contiguous palindromic substring.
  • Counting total palindromic substrings.

Algorithmic Decision Tree:

  • Expand Around Center
  • Manacher's Linear Palindrome Algorithm
  • 2D DP Palindrome Table

Connected Patterns:

Palindromic SubstringsLongest Palindromic SubsequenceShortest Palindrome

1. 2D Dynamic Programming Table

Intuition

Let dp[i][j] be true if s[i...j] is a palindrome. A substring s[i...j] is a palindrome if s[i] == s[j] and either j - i <= 2 or dp[i+1][j-1] is true. Fill the table for lengths from 1 to N, tracking the maximum length and start index.

When to apply: When laying out the DP state transition for substring palindromes.

Algorithm

  1. Initialize dp[n][n] = false.
  2. Set start = 0, maxLen = 1.
  3. Loop len from 1 to n:
  4. Loop i from 0 to n - len:
  5. j = i + len - 1
  6. If s[i] == s[j] and (len <= 2 or dp[i + 1][j - 1]):
  7. dp[i][j] = true
  8. If len > maxLen: maxLen = len, start = i.
  9. Return s.substr(start, maxLen).

2D Dynamic Programming Table

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, a, b, a, d]
Current operationSTEP 1 OF 6
Observation: Define boolean table isPal[i][j] indicating if s[i
Visual state
Values and pointers at this exact step
array
S
b
a
b
a
d
0
↑ DIAGONAL: len=1
1
2
3
4
Variables at this step
len
1
maxLen
1
longest
b
baseFilled
true
Check / comparison
Initialize isPal[5][5]. Single characters are always palindromes.
Decision / next transition
isPal[i][i] = true for all i. maxLen = 1, longest = 'b'.
Why this step matters

Observation: Define boolean table isPal[i][j] indicating if s[i..j] is palindromic.

Decision: Base case: Every single letter is palindromic. Set isPal[i][i] = true and initialize maxLen = 1.

Invariant: All 1-length substrings satisfy the palindrome definition trivially.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string longestPalindrome(std::string s) {
8 int n = s.size();
9 if (n <= 1) return s;
10
11 std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
12 int start = 0, maxLen = 1;
13
14 for (int i = 0; i < n; ++i) dp[i][i] = true;
15
16 for (int len = 2; len <= n; ++len) {
17 for (int i = 0; i <= n - len; ++i) {
18 int j = i + len - 1;
19 if (s[i] == s[j]) {
20 if (len == 2 || dp[i + 1][j - 1]) {
21 dp[i][j] = true;
22 if (len > maxLen) {
23 start = i;
24 maxLen = len;
25 }
26 }
27 }
28 }
29 }
30 return s.substr(start, maxLen);
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << sol.longestPalindrome("babad") << std::endl; // "bab" or "aba"
37 std::cout << sol.longestPalindrome("cbbd") << std::endl; // "bb"
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N^2) — Fills an N x N boolean matrix.
  • Space complexity: O(N^2)

Why Brute Force Doesn't Scale:

Expanding around centers avoids allocating an N x N DP table, reducing space to O(1).

Manacher's Algorithm provides strictly linear O(N) time with minimal auxiliary memory.

2. Expand Around Center (O(1) Space)

Intuition

For every index i from 0 to n - 1, expand outward around center (i, i) to find the longest odd-length palindrome, and around (i, i + 1) to find the longest even-length palindrome. Maintain global start and maxLen.

When to apply: The gold standard interview solution combining minimal code, optimal space, and high speed.

Algorithm

  1. Define helper expand(left, right):
  2. - While left >= 0 and right < n and s[left] == s[right]: left--, right++.
  3. - Return length right - left - 1.
  4. Loop i from 0 to n - 1:
  5. len1 = expand(i, i)
  6. len2 = expand(i, i + 1)
  7. len = max(len1, len2)
  8. If len > maxLen: update maxLen = len, start = i - (len - 1) / 2.
  9. Return s.substr(start, maxLen).

Expand Around Center (O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, a, b, a, d]
Current operationSTEP 1 OF 6
Observation: Every palindrome has a center
Visual state
Values and pointers at this exact step
array
S
b
a
b
a
d
0
↑ CENTER 0: 'b'
1
2
3
4
Variables at this step
center
0
oddLen
1
evenLen
0
longest
b
maxLen
1
Check / comparison
Expand odd center at i=0 ('b'). Boundary reached immediately.
Decision / next transition
Palindrome length = 1 ('b'). maxLen = 1.
Why this step matters

Observation: Every palindrome has a center. There are 2N - 1 = 9 potential centers (5 odd, 4 even).

Decision: Test center at index 0: odd expansion yields 'b' (len 1). Even expansion yields len 0.

Invariant: Expanding around centers checks all symmetric spans without allocating auxiliary tables.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6 int expandAroundCenter(const std::string& s, int left, int right) {
7 int n = s.size();
8 while (left >= 0 && right < n && s[left] == s[right]) {
9 left--;
10 right++;
11 }
12 return right - left - 1;
13 }
14public:
15 std::string longestPalindrome(std::string s) {
16 int n = s.size();
17 if (n <= 1) return s;
18
19 int start = 0, maxLen = 0;
20 for (int i = 0; i < n; ++i) {
21 int len1 = expandAroundCenter(s, i, i); // Odd length
22 int len2 = expandAroundCenter(s, i, i + 1); // Even length
23 int len = std::max(len1, len2);
24 if (len > maxLen) {
25 maxLen = len;
26 start = i - (len - 1) / 2;
27 }
28 }
29 return s.substr(start, maxLen);
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.longestPalindrome("babad") << std::endl; // "bab"
36 std::cout << sol.longestPalindrome("cbbd") << std::endl; // "bb"
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N^2) — Tests 2N - 1 centers, expanding up to N / 2 steps each with O(1) extra memory.
  • Space complexity: O(1) auxiliary space

3. Manacher's Algorithm (Strictly O(N) Linear Time)

Intuition

Preprocess string s into T by inserting # between characters (e.g., ^#a#b#a#$) so that all palindromes become odd-length. Maintain C (center) and R (right boundary). For current index i, initialize P[i] = (R > i) ? min(R - i, P[2 * C - i]) : 0. Expand P[i] as far as characters match, and update C and R when i + P[i] > R.

When to apply: When input size N >= 105 and strict O(N) runtime is required.

Algorithm

  1. Transform s into T = '^#' + s.join('#') + '#$'.
  2. Initialize P array of size T.length with 0, C = 0, R = 0.
  3. Loop i from 1 to T.length - 2:
  4. iMirror = 2 * C - i
  5. If R > i: P[i] = min(R - i, P[iMirror]).
  6. While T[i + 1 + P[i]] == T[i - 1 - P[i]]: P[i]++.
  7. If i + P[i] > R: C = i, R = i + P[i].
  8. Find maximum in P, map center and radius back to original string index, and return substring.

Odd and Even Center Expansion Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, a, b, a, d]
Current operationSTEP 1 OF 6
Observation: Center at i = 0 ('b')
Visual state
Values and pointers at this exact step
array
S
b
a
b
a
d
0
↑ Center i=0 ('b')
1
2
3
4
Variables at this step
center
0
oddPalindrome
b
len
1
maxLen
1
bestSubstr
b
Why this step matters

Observation: Center at i = 0 (b). Expands 0 steps left.

Decision: Substring "b" has length 1. Initialize best = "b".

Invariant: Single character is valid palindrome.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string longestPalindrome(std::string s) {
9 if (s.empty()) return "";
10
11 std::string T = "^";
12 for (char c : s) {
13 T += "#";
14 T += c;
15 }
16 T += "#$";
17
18 int n = T.size();
19 std::vector<int> P(n, 0);
20 int C = 0, R = 0;
21
22 for (int i = 1; i < n - 1; ++i) {
23 int iMirror = 2 * C - i;
24 if (R > i) {
25 P[i] = std::min(R - i, P[iMirror]);
26 }
27 while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
28 P[i]++;
29 }
30 if (i + P[i] > R) {
31 C = i;
32 R = i + P[i];
33 }
34 }
35
36 int maxLen = 0, centerIndex = 0;
37 for (int i = 1; i < n - 1; ++i) {
38 if (P[i] > maxLen) {
39 maxLen = P[i];
40 centerIndex = i;
41 }
42 }
43
44 int start = (centerIndex - maxLen) / 2;
45 return s.substr(start, maxLen);
46 }
47};
48
49int main() {
50 Solution sol;
51 std::cout << sol.longestPalindrome("babad") << std::endl; // "bab" or "aba"
52 std::cout << sol.longestPalindrome("cbbd") << std::endl; // "bb"
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N) strictly — Each character comparison advances the right boundary R, which only moves from 0 to 2N + 3.
  • Space complexity: O(N) for transformed string and radius table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.2D Dynamic Programming TableO(N^2)O(N^2)Systematic table formulation dp[i][j] = (s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])).Consumes O(N2) memory.
2.Expand Around Center (Optimal in Interviews)O(N^2)O(1) extra spaceZero auxiliary memory, extremely concise, fastest in practice for N <= 1000.Quadratic time on strings with all identical characters.
3.Manacher's AlgorithmOptimalO(N) strictlyO(N)Guaranteed linear time string palindrome search.More complex to write on a whiteboard.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking only odd centers (i, i) and omitting even centers (i, i+1).

Pitfall 2:

Calculating substring start index incorrectly from expanded pointer values.

Crucial Edge Cases to Validate:

  • Entire string is a palindrome (e.g. racecar): Expands fully from center index 3 to reach both ends, returning full string.
  • Even-length palindrome (e.g. cbbd): Even-length center expansion expand(1, 2) successfully captures bb.
  • Single character string (s = a): Returns immediately as a.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the Expand Around Center approach as the primary optimal interview solution due to O(1) space.
  2. Mention Manacher's Algorithm as a theoretical O(N) linear time optimization.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are there 2N - 1 centers to check in a string of length N?

Back to DSA Sheet