1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/**
 * Find the longest palindromic substring in a string.
 * Expand Around Center approach.
 * 
 * @param {string} s - The input string
 * @return {string} - The longest palindromic substring
 */
function longestPalindrome(s) {
  if (!s || s.length < 2) {
    return s;
  }
  
  let start = 0;
  let maxLength = 1;
  
  // Helper function to expand around center
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    
    // Return the length of the palindrome
    return right - left - 1;
  }
  
  for (let i = 0; i < s.length; i++) {
    // Expand for odd-length palindromes
    const len1 = expandAroundCenter(i, i);
    
    // Expand for even-length palindromes
    const len2 = expandAroundCenter(i, i + 1);
    
    // Find the maximum length
    const len = Math.max(len1, len2);
    
    // Update the longest palindrome if needed
    if (len > maxLength) {
      maxLength = len;
      start = i - Math.floor((len - 1) / 2);
    }
  }
  
  return s.substring(start, start + maxLength);
}
 
/**
 * Find the longest palindromic substring in a string.
 * Dynamic Programming approach.
 * 
 * @param {string} s - The input string
 * @return {string} - The longest palindromic substring
 */
function longestPalindromeDP(s) {
  const n = s.length;
  if (n <= 1) {
    return s;
  }
  
  // Create a DP table
  const dp = Array(n).fill().map(() => Array(n).fill(false));
  
  let start = 0;
  let maxLength = 1;
  
  // All single characters are palindromes
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  
  // Check for palindromes of length 2
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLength = 2;
    }
  }
  
  // Check for palindromes of length 3 or more
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        
        if (len > maxLength) {
          maxLength = len;
          start = i;
        }
      }
    }
  }
  
  return s.substring(start, start + maxLength);
}
 
/**
 * Find the longest palindromic substring in a string.
 * Manacher's Algorithm.
 * 
 * @param {string} s - The input string
 * @return {string} - The longest palindromic substring
 */
function longestPalindromeManacher(s) {
  if (!s || s.length < 2) {
    return s;
  }
  
  // Transform the string
  let t = '#';
  for (let i = 0; i < s.length; i++) {
    t += s[i] + '#';
  }
  
  const n = t.length;
  const P = Array(n).fill(0);
  
  let C = 0;  // Center of the rightmost palindrome
  let R = 0;  // Right boundary of the rightmost palindrome
  let maxLen = 0;
  let centerIndex = 0;
  
  for (let i = 0; i < n; i++) {
    // Mirror of i with respect to C
    const mirror = 2 * C - i;
    
    // If i is within the right boundary, use the mirror value
    if (i < R) {
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    // Expand around center i
    let left = i - (P[i] + 1);
    let right = i + (P[i] + 1);
    
    while (left >= 0 && right < n && t[left] === t[right]) {
      P[i]++;
      left--;
      right++;
    }
    
    // Update C and R if the palindrome centered at i expands beyond R
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
    
    // Update the longest palindrome
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  
  // Convert back to the original string format
  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}
 
// Test cases
console.log(longestPalindrome("babad"));  // "bab" or "aba"
console.log(longestPalindrome("cbbd"));   // "bb"
console.log(longestPalindrome("racecar"));  // "racecar"
 
console.log(longestPalindromeDP("babad"));  // "bab" or "aba"
console.log(longestPalindromeDP("cbbd"));   // "bb"
console.log(longestPalindromeDP("racecar"));  // "racecar"
 
console.log(longestPalindromeManacher("babad"));  // "bab" or "aba"
console.log(longestPalindromeManacher("cbbd"));   // "bb"
console.log(longestPalindromeManacher("racecar"));  // "racecar"