This approach is based on the observation that a palindrome mirrors around its center. Therefore, if we choose a center, we can expand outward to check for the longest possible palindrome. We can have centers between each two characters as well as on each character to cater for even and odd length palindromes.
Time Complexity: O(n^2) because we potentially expand around n centers.
Space Complexity: O(1), aside from the space required for the output string.
1#include <stdio.h>
2#include <string.h>
3
4int expandAroundCenter(char *s, int left, int right) {
5 while (left >= 0 && right < strlen(s) && s[left] == s[right]) {
6 left--;
7 right++;
8 }
9 return right - left - 1;
10}
11
12char * longestPalindrome(char * s){
13 if (s == NULL || strlen(s) < 1) return "";
14 int start = 0, end = 0;
15 for (int i = 0; i < strlen(s); i++) {
16 int len1 = expandAroundCenter(s, i, i);
17 int len2 = expandAroundCenter(s, i, i + 1);
18 int len = len1 > len2 ? len1 : len2;
19 if (len > end - start) {
20 start = i - (len - 1) / 2;
21 end = i + len / 2;
22 }
23 }
24 char *result = (char *)malloc(end - start + 2);
25 strncpy(result, &s[start], end - start + 1);
26 result[end - start + 1] = '\0';
27 return result;
28}The solution iterates over each character, considering it as a possible center of a palindrome. It tries to expand around it for both odd and even lengths. We maintain the longest found palindrome's start and end indices, which are used to construct the result substring in the end.
In this approach, a 2D DP table is constructed where dp[i][j] is true if the string s[i...j] is a palindrome. Each entry is dependent on smaller substring checks. This method leverages overlapping subproblems.
Time Complexity: O(n^2) due to the complete 2D table scan.
Space Complexity: O(n^2) as the DP table fully holds substring truths.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5char *longestPalindrome(char *s) {
6 int n = strlen(s);
7 if (n == 0) return "";
8 int start = 0, maxLength = 1;
9 int **dp = (int **)malloc(n * sizeof(int *));
10 for (int i = 0; i < n; i++) {
11 dp[i] = (int *)malloc(n * sizeof(int));
12 memset(dp[i], 0, n * sizeof(int));
13 }
14 for (int i = 0; i < n; i++) dp[i][i] = 1;
15 for (int begin = n - 1; begin >= 0; begin--) {
16 for (int end = begin + 1; end < n; end++) {
17 if (s[begin] == s[end]) {
18 if (end - begin == 1 || dp[begin + 1][end - 1]) {
19 dp[begin][end] = 1;
20 if (end - begin + 1 > maxLength) {
21 start = begin;
22 maxLength = end - begin + 1;
23 }
24 }
25 }
26 }
27 }
28 char *result = (char *)malloc(maxLength + 1);
29 strncpy(result, s + start, maxLength);
30 result[maxLength] = '\0';
31 for (int i = 0; i < n; i++) free(dp[i]);
32 free(dp);
33 return result;
34}We make use of a DP table that captures the palindrome status for each (i,j) substring. The status gets updated from prior adjacent matches. Substring boundaries clarify palindromes, storing the starting position and length of the longest identified palindrome.