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 <string>
2class Solution {
3public:
4 std::string longestPalindrome(std::string s) {
5 if (s.empty()) return "";
6 int start = 0, end = 0;
7 for (int i = 0; i < s.size(); i++) {
8 int len1 = expandAroundCenter(s, i, i);
9 int len2 = expandAroundCenter(s, i, i + 1);
10 int len = std::max(len1, len2);
11 if (len > end - start) {
12 start = i - (len - 1) / 2;
13 end = i + len / 2;
14 }
15 }
16 return s.substr(start, end - start + 1);
17 }
18private:
19 int expandAroundCenter(const std::string &s, int left, int right) {
20 while (left >= 0 && right < s.size() && s[left] == s[right]) {
21 left--;
22 right++;
23 }
24 return right - left - 1;
25 }
26};The implementation is similar to the C solution but uses C++ string methods for slicing and character operations, making the implementation more concise. Both single character centers and pairs of characters are considered.
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.
1function longestPalindrome(s) {
2 let n = s.length;
3 if (n === 0) return "";
4 let dp = Array.from(Array(n), () => Array(n).fill(false));
5 let start = 0;
6 let maxLength = 1;
7
8 for (let i = 0; i < n; i++) dp[i][i] = true;
9
10 for (let begin = n - 1; begin >= 0; begin--) {
11 for (let end = begin + 1; end < n; end++) {
12 if (s[begin] === s[end]) {
13 if (end - begin === 1 || dp[begin + 1][end - 1]) {
14 dp[begin][end] = true;
15 if (end - begin + 1 > maxLength) {
16 start = begin;
17 maxLength = end - begin + 1;
18 }
19 }
20 }
21 }
22 }
23 return s.substring(start, start + maxLength);
24}The JavaScript approach executes by deploying a 2D matrix to record palindromic potential. Here, characters corresponding with identical value alignment confirm pattern validity recursively updated upon through iteration.