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.
1public class Solution {
2 public string LongestPalindrome(string s) {
3 if (s == null || s.Length < 1) return "";
4 int start = 0, end = 0;
5 for (int i = 0; i < s.Length; i++) {
6 int len1 = ExpandAroundCenter(s, i, i);
7 int len2 = ExpandAroundCenter(s, i, i + 1);
8 int len = Math.Max(len1, len2);
9 if (len > end - start) {
10 start = i - (len - 1) / 2;
11 end = i + len / 2;
12 }
13 }
14 return s.Substring(start, end - start + 1);
15 }
16
17 private int ExpandAroundCenter(string s, int left, int right) {
18 while (left >= 0 && right < s.Length && s[left] == s[right]) {
19 left--;
20 right++;
21 }
22 return right - left - 1;
23 }
24}The C# solution uses similar reasoning as the others, with the palindrome centers enabling the expansion on direct character or paired centers. Calculation of the longest span helps determine the key indices for substring formation.
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 <string>
2#include <vector>
3class Solution {
4public:
5 std::string longestPalindrome(std::string s) {
6 int n = s.size();
7 if (n == 0) return "";
8 std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
9 int start = 0, maxLength = 1;
10 for (int i = 0; i < n; i++) dp[i][i] = 1;
11 for (int begin = n - 1; begin >= 0; begin--) {
12 for (int end = begin + 1; end < n; end++) {
13 if (s[begin] == s[end]) {
14 if (end - begin == 1 || dp[begin + 1][end - 1]) {
15 dp[begin][end] = 1;
16 if (end - begin + 1 > maxLength) {
17 start = begin;
18 maxLength = end - begin + 1;
19 }
20 }
21 }
22 }
23 }
24 return s.substr(start, maxLength);
25 }
26};The DP solution is carried out with a 2D table capturing palindrome truths and unit tests. As the start and end values are determined, the length is monitored to catch the longest palindromic string upwards.