C++ - Longest Palindromic Substring
Problem Statement
Given a string s, find the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "aba" // or "bab"
Example 2:
Input: s = "cbbd"
Output: "bb"
Approach 1: Dynamic Programming (O(N²) Time, O(N²) Space)
Define dp[i][j] → true if substring s[i:j] is a palindrome.
Transition:
Base case: Single-character substrings are palindromes.
Expand when s[i] == s[j]:
(if substring between is also palindrome)
dp[i][j]=dp[i+1][j−1](if substring between is also palindrome)
Track the longest palindrome found.
Code Implementation
#include <iostream>
#include <vector>
using namespace std;
string longestPalindrome(string s) {
int n = s.size();
if (n == 0) return "";
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, maxLength = 1;
// Every single character is a palindrome
for (int i = 0; i < n; i++) dp[i][i] = true;
// Check for two-character substrings
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = true;
start = i;
maxLength = 2;
}
}
// Check for substrings of length 3 or more
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;
maxLength = len;
}
}
}
return s.substr(start, maxLength);
}
int main() {
string s = "babad";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
return 0;
}
Time Complexity:
O(N²) (Nested loops).
Space Complexity:
O(N²) (DP table storage).
Approach 2: Expand Around Center (O(N²) Time, O(1) Space)
Expand outward from each character and each pair of adjacent characters.
Keep track of the longest palindrome found.
Code Implementation
#include <iostream>
using namespace std;
string expandAroundCenter(string s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
string longestPalindrome(string s) {
if (s.empty()) return "";
string longest = "";
for (int i = 0; i < s.size(); i++) {
string oddPalindrome = expandAroundCenter(s, i, i); // Odd-length
string evenPalindrome = expandAroundCenter(s, i, i + 1); // Even-length
if (oddPalindrome.size() > longest.size()) longest = oddPalindrome;
if (evenPalindrome.size() > longest.size()) longest = evenPalindrome;
}
return longest;
}
int main() {
string s = "cbbd";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
return 0;
}
Time Complexity:
O(N²) (Expanding for every index).
Space Complexity:
O(1) (No extra space used).
Approach 3: Manacher's Algorithm (O(N) Time, O(N) Space)
Uses a special transformation (# inserted between characters).
Efficient for large strings.
Code Implementation
#include <iostream>
#include <vector>
using namespace std;
string preprocess(string s) {
string t = "#";
for (char c : s) {
t += c;
t += "#";
}
return t;
}
string longestPalindrome(string s) {
if (s.empty()) return "";
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0);
int c = 0, r = 0, maxLen = 0, center = 0;
for (int i = 0; i < n; i++) {
int mirror = 2 * c - i;
if (i < r) p[i] = min(r - i, p[mirror]);
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] == t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > r) {
c = i;
r = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
center = i;
}
}
int start = (center - maxLen) / 2;
return s.substr(start, maxLen);
}
int main() {
string s = "babad";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
return 0;
}
