Longest Palindromic Substring
Problem Statement
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba"
is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consists of only digits and English letters.
Approaches
Expand Around Center Approach
Explanation:
- Every palindrome is centered at either a single character or a pair of characters.
- Expand around each center to find the longest palindrome, checking both odd-length and even-length cases.
- This approach is efficient with
O(n^2)
time complexity andO(1)
space complexity.
public class Solution {
public string LongestPalindrome(string s) {
if (string.IsNullOrEmpty(s) || s.Length < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.Length; i++) {
int len1 = ExpandFromCenter(s, i, i); // Odd-length palindromes
int len2 = ExpandFromCenter(s, i, i + 1); // Even-length palindromes
int len = Math.Max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.Substring(start, end - start + 1);
}
private int ExpandFromCenter(string s, int left, int right) {
while (left >= 0 && right < s.Length && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1; // Length of the palindrome
}
}
Dynamic Programming Approach
Explanation:
- Use a 2D table
dp
wheredp[i][j]
istrue
if the substrings[i...j]
is a palindrome. - Transition:
dp[i][j] = true
ifs[i] == s[j]
anddp[i+1][j-1]
is true (or if the length is less than 3).
- Track the longest palindrome during the process.
- Time Complexity:
O(n^2)
- Space Complexity:
O(n^2)
public class Solution {
public string LongestPalindrome(string s) {
if (s == null || s.Length == 0) return "";
int n = s.Length;
bool[,] dp = new bool[n, n];
int start = 0, maxLength = 0;
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i, j] = (len == 1 || len == 2) || dp[i + 1, j - 1];
if (dp[i, j] && len > maxLength) {
start = i;
maxLength = len;
}
}
}
}
return s.Substring(start, maxLength);
}
}
Brute Force Approach
Explanation:
- Check all substrings of
s
to determine if they are palindromic. - This is inefficient for large input sizes.
- Time Complexity:
O(n^3)
- Space Complexity:
O(1)
public class Solution {
public string LongestPalindrome(string s) {
if (s == null || s.Length == 0) return "";
string longest = "";
for (int i = 0; i < s.Length; i++) {
for (int j = i; j < s.Length; j++) {
if (IsPalindrome(s, i, j) && (j - i + 1 > longest.Length)) {
longest = s.Substring(i, j - i + 1);
}
}
}
return longest;
}
private bool IsPalindrome(string s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
}
Complexity Analysis
Expand Around Center:
- Time Complexity:
O(n^2)
— Each center expansion takesO(n)
, and there areO(n)
centers. - Space Complexity:
O(1)
.
Dynamic Programming:
- Time Complexity:
O(n^2)
— Filling the DP table. - Space Complexity:
O(n^2)
— Storing the DP table.
Brute Force:
- Time Complexity:
O(n^3)
— Checking all substrings and validating each palindrome. - Space Complexity:
O(1)
.
Example Outputs
Example 1:
Input: s = "babad"
Output: "bab"
or "aba"
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = ""
Output: ""
Example 4:
Input: s = "a"
Output: "a"