StringProblem 8 of 43
Write a program to find the longest Palindrome in a string - Longest palindromic Substring
Problem Statement
Given a string s, find the longest palindromic substring in s.
Example:
-
Input:
"babad" -
Output:
"bab"or"aba"(both are valid) -
Input:
"cbbd" -
Output:
"bb" -
Input:
"a" -
Output:
"a"
Approach 1: Brute Force
Intuition
Generate all possible substrings and check if each one is a palindrome. Keep track of the longest palindrome found.
Algorithm
- Generate all substrings (n² substrings)
- For each substring, check if it's a palindrome (O(n) check)
- Track the longest palindrome
java
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
int maxLen = 1;
int start = 0;
// Check all substrings
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPalindrome(s, i, j)) {
int len = j - i + 1;
if (len > maxLen) {
maxLen = len;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n³) - O(n²) substrings × O(n) palindrome check
- Space Complexity: O(1) - Only using constant extra space
Approach 2: Expand Around Center (Optimal)
Intuition
A palindrome mirrors around its center. We can expand around each potential center and find the longest palindrome. There are 2n-1 centers (n single character centers + n-1 between-character centers for even-length palindromes).
Algorithm
- For each index i (0 to n-1):
- Expand around center i (odd length palindromes)
- Expand around center between i and i+1 (even length palindromes)
- Track the longest palindrome found
- Return the longest palindrome
java
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
int start = 0;
int maxLen = 1;
for (int i = 0; i < n; i++) {
// Odd length palindromes (single center)
int len1 = expandAroundCenter(s, i, i);
// Even length palindromes (double center)
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}Complexity Analysis
- Time Complexity: O(n²) - n centers × O(n) expansion each
- Space Complexity: O(1) - Only using constant extra space
Approach 3: Dynamic Programming
Intuition
Use a 2D DP table where dp[i][j] represents whether substring s[i...j] is a palindrome.
A substring is a palindrome if:
- Characters at both ends are equal:
s[i] == s[j] - The inner substring is also a palindrome:
dp[i+1][j-1] == true
Algorithm
- All single characters are palindromes:
dp[i][i] = true - Check two-character substrings:
dp[i][i+1] = (s[i] == s[i+1]) - For length 3 and above:
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1] - Track the longest palindrome
java
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
// dp[i][j] = true if s[i..j] is palindrome
boolean[][] dp = new boolean[n][n];
int start = 0;
int maxLen = 1;
// All single characters are palindromes
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check two-character substrings
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;
}
}
// Check substrings of length 3 and more
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);
}
}Complexity Analysis
- Time Complexity: O(n²) - Filling n² DP table
- Space Complexity: O(n²) - For the DP table
Approach 4: Manacher's Algorithm (Most Optimal)
Intuition
Manacher's algorithm achieves O(n) time by cleverly using previously computed palindrome information to avoid redundant comparisons.
Complexity Analysis
- Time Complexity: O(n) - Linear time
- Space Complexity: O(n) - For transformed string and array
Key Takeaways
- Expand around center is the most intuitive O(n²) approach
- There are 2n-1 centers to consider (n odd + n-1 even length palindromes)
- Dynamic Programming trades space for cleaner code but same time complexity
- Manacher's Algorithm achieves O(n) time but is more complex to implement
- For interviews, expand around center is usually the expected solution
- Always handle edge cases: empty string, single character, all same characters