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.
1function longestPalindrome(s) {
2 if (!s || s.length < 1) return "";
3 let start = 0, end = 0;
4 for (let i = 0; i < s.length; i++) {
5 let len1 = expandAroundCenter(s, i, i);
6 let len2 = expandAroundCenter(s, i, i + 1);
7 let len = Math.max(len1, len2);
8 if (len > end - start) {
9 start = i - Math.floor((len - 1) / 2);
10 end = i + Math.floor(len / 2);
11 }
12 }
13 return s.substring(start, end + 1);
14}
15
16function expandAroundCenter(s, left, right) {
17 while (left >= 0 && right < s.length && s[left] === s[right]) {
18 left--;
19 right++;
20 }
21 return right - left - 1;
22}This JavaScript solution operates via expanding around each center. The goal is to evaluate both single and double centered expansions across characters to establish the longest palindrome segment.
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.
1class Solution {
2 public String longestPalindrome(String s) {
3 int n = s.length();
4 if (n == 0) return "";
5 boolean[][] dp = new boolean[n][n];
6 int maxLength = 1;
7 int start = 0;
8
9 for (int i = 0; i < n; i++) dp[i][i] = true;
10
11 for (int begin = n - 1; begin >= 0; begin--) {
12 for (int end = begin + 1; end < n; end++) {
13 if (s.charAt(begin) == s.charAt(end)) {
14 if (end - begin == 1 || dp[begin + 1][end - 1]) {
15 dp[begin][end] = true;
16 if (end - begin + 1 > maxLength) {
17 start = begin;
18 maxLength = end - begin + 1;
19 }
20 }
21 }
22 }
23 }
24 return s.substring(start, start + maxLength);
25 }
26}In Java, we construct a 2D table of boolean values to represent substring palindrome status and update them progressively by leveraging smaller subproblem solutions.