# 1st Method :- Expand Around Center \uD83D\uDEA9\n## Intuition \uD83D\uDE80:\n\nThe intuition behind this code is to find the longest palindromic substring within a given input string `s`. A palindromic substring is a string that reads the same forwards and backward. To achieve this, the code explores the input string character by character, checking both odd and even-length palindromes by expanding around the center of each character and updating the longest palindrome found so far.\n\n## Approach \uD83D\uDE80:\n\n1. **Initialization**: \n - Check if the input string `s` is empty. If it is, return an empty string because there can\'t be any palindromes in an empty string.\n - Initialize a variable `longestPalindromeIndices` to store the indices of the longest palindrome found. Initially, it\'s set to [0, 0].\n\n2. **Main Loop**:\n - Iterate through the characters of the input string `s` using a for loop.\n\n3. **Odd-Length Palindromes**:\n - For each character at position `i`, check if there is a palindrome centered at that character. This is done by calling the `expandAroundCenter` function with `i` as both the start and end positions.\n - If a longer palindrome is found than the current longest one, update `longestPalindromeIndices` with the new indices.\n\n4. **Even-Length Palindromes**:\n - Check if there is a palindrome centered between the characters at positions `i` and `i + 1`. This is done by calling the `expandAroundCenter` function with `i` as the start position and `i + 1` as the end position.\n - If a longer even-length palindrome is found, update `longestPalindromeIndices` with the new indices.\n\n5. **Continuation**:\n - Continue this process for all characters in the input string. By the end of the loop, you will have identified the indices of the longest palindromic substring.\n\n6. **Result Extraction**:\n - Finally, extract the longest palindromic substring from the input string `s` using the indices obtained in `longestPalindromeIndices`.\n - Return this extracted substring as the result.\n\nThe key idea is to systematically explore the input string, checking both odd and even-length palindromes by expanding around the center of each character and maintaining the information about the longest palindrome found throughout the process. This approach ensures that you find the maximum length palindromic substring within the input string.\n## Complexity \uD83D\uDE81\n### \uD83C\uDFF9 Time complexity: O(N^2)\n\n1. The `expandAroundCenter` function has a time complexity of O(N), where N is the length of the input string `s`. This is because in the worst case, it can expand all the way to the ends of the string.\n2. The `longestPalindrome` function iterates through the characters of the string, and for each character, it may call `expandAroundCenter` once or twice (in the case of even-length palindromes). Therefore, the time complexity of the `longestPalindrome` function is O(N^2).\n\nSo, the overall time complexity of the code is O(N^2) due to the nested loops in the `longestPalindrome` function.\n\n### \uD83C\uDFF9 Space complexity: O(1)\n\nThe space complexity is primarily determined by the additional space used for variables and the recursive call stack.\n\n1. The `expandAroundCenter` function uses a constant amount of extra space, so its space complexity is O(1).\n2. The `longestPalindrome` function uses a few additional integer variables to store indices, but the space used by these variables is also constant, so its space complexity is O(1).\n3. The recursive calls in the `expandAroundCenter` function do not use significant additional space because they are tail-recursive. The stack space used by these calls is O(1).\n\nSo, the overall space complexity of the code is O(1).\n\n## Code \u2712\uFE0F\n``` Java []\nclass Solution {\n public String longestPalindrome(String s) {\n // Check if the input string is empty, return an empty string if so\n if (s.isEmpty())\n return "";\n\n // Initialize variables to store the indices of the longest palindrome found\n int[] longestPalindromeIndices = { 0, 0 };\n\n // Loop through the characters in the input string\n for (int i = 0; i < s.length(); ++i) {\n // Find the indices of the longest palindrome centered at character i\n int[] currentIndices = expandAroundCenter(s, i, i);\n\n // Compare the length of the current palindrome with the longest found so far\n if (currentIndices[1] - currentIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the current one is longer\n longestPalindromeIndices = currentIndices;\n }\n\n // Check if there is a possibility of an even-length palindrome centered at\n // character i and i+1\n if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {\n // Find the indices of the longest even-length palindrome centered at characters\n // i and i+1\n int[] evenIndices = expandAroundCenter(s, i, i + 1);\n\n // Compare the length of the even-length palindrome with the longest found so\n // far\n if (evenIndices[1] - evenIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the even-length one is longer\n longestPalindromeIndices = evenIndices;\n }\n }\n }\n\n // Extract and return the longest palindrome substring using the indices\n return s.substring(longestPalindromeIndices[0], longestPalindromeIndices[1] + 1);\n }\n\n // Helper function to find and return the indices of the longest palindrome\n // extended from s[i..j] (inclusive) by expanding around the center\n private int[] expandAroundCenter(final String s, int i, int j) {\n // Expand the palindrome by moving outward from the center while the characters\n // match\n while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {\n i--; // Move the left index to the left\n j++; // Move the right index to the right\n }\n // Return the indices of the longest palindrome found\n return new int[] { i + 1, j - 1 };\n }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n std::string longestPalindrome(std::string s) {\n // Check if the input string is empty, return an empty string if so\n if (s.empty())\n return "";\n\n // Initialize variables to store the indices of the longest palindrome found\n std::vector longestPalindromeIndices = {0, 0};\n\n for (int i = 0; i < s.length(); ++i) {\n // Find the indices of the longest palindrome centered at character i\n std::vector currentIndices = expandAroundCenter(s, i, i);\n\n // Compare the length of the current palindrome with the longest found so far\n if (currentIndices[1] - currentIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n longestPalindromeIndices = currentIndices;\n }\n\n // Check if there is a possibility of an even-length palindrome centered at\n // character i and i+1\n if (i + 1 < s.length() && s[i] == s[i + 1]) {\n // Find the indices of the longest even-length palindrome centered at characters\n // i and i+1\n std::vector evenIndices = expandAroundCenter(s, i, i + 1);\n\n // Compare the length of the even-length palindrome with the longest found so far\n if (evenIndices[1] - evenIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n longestPalindromeIndices = evenIndices;\n }\n }\n }\n\n // Extract and return the longest palindrome substring using the indices\n return s.substr(longestPalindromeIndices[0], longestPalindromeIndices[1] - longestPalindromeIndices[0] + 1);\n }\n\nprivate:\n // Helper function to find and return the indices of the longest palindrome\n // extended from s[i..j] (inclusive) by expanding around the center\n std::vector expandAroundCenter(const std::string &s, int i, int j) {\n while (i >= 0 && j < s.length() && s[i] == s[j]) {\n --i;\n ++j;\n }\n return {i + 1, j - 1};\n }\n};\n\n```\n``` Python []\nclass Solution:\n def longestPalindrome(self, s: str) -> str:\n # Check if the input string is empty, return an empty string if so\n if not s:\n return ""\n\n # Initialize variables to store the indices of the longest palindrome found\n longest_palindrome_indices = [0, 0]\n\n def expand_around_center(s, i, j):\n # Helper function to find and return the indices of the longest palindrome\n # extended from s[i..j] (inclusive) by expanding around the center\n while i >= 0 and j < len(s) and s[i] == s[j]:\n i -= 1\n j += 1\n return [i + 1, j - 1]\n\n for i in range(len(s)):\n current_indices = expand_around_center(s, i, i)\n\n # Compare the length of the current palindrome with the longest found so far\n if current_indices[1] - current_indices[0] > longest_palindrome_indices[1] - longest_palindrome_indices[0]:\n longest_palindrome_indices = current_indices\n\n if i + 1 < len(s) and s[i] == s[i + 1]:\n even_indices = expand_around_center(s, i, i + 1)\n\n # Compare the length of the even-length palindrome with the longest found so far\n if even_indices[1] - even_indices[0] > longest_palindrome_indices[1] - longest_palindrome_indices[0]:\n longest_palindrome_indices = even_indices\n\n # Extract and return the longest palindrome substring using the indices\n return s[longest_palindrome_indices[0]:longest_palindrome_indices[1] + 1]\n\n```\n``` JavaScript []\nvar longestPalindrome = function(s) {\n // Check if the input string is empty, return an empty string if so\n if (s.length === 0)\n return "";\n\n // Initialize variables to store the indices of the longest palindrome found\n let longestPalindromeIndices = [0, 0];\n\n // Loop through the characters in the input string\n for (let i = 0; i < s.length; ++i) {\n // Find the indices of the longest palindrome centered at character i\n let currentIndices = expandAroundCenter(s, i, i);\n\n // Compare the length of the current palindrome with the longest found so far\n if (currentIndices[1] - currentIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the current one is longer\n longestPalindromeIndices = currentIndices;\n }\n\n // Check if there is a possibility of an even-length palindrome centered at\n // character i and i+1\n if (i + 1 < s.length && s[i] === s[i + 1]) {\n // Find the indices of the longest even-length palindrome centered at characters\n // i and i+1\n let evenIndices = expandAroundCenter(s, i, i + 1);\n\n // Compare the length of the even-length palindrome with the longest found so\n // far\n if (evenIndices[1] - evenIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the even-length one is longer\n longestPalindromeIndices = evenIndices;\n }\n }\n }\n\n // Extract and return the longest palindrome substring using the indices\n return s.slice(longestPalindromeIndices[0], longestPalindromeIndices[1] + 1);\n}\n\n// Helper function to find and return the indices of the longest palindrome\n// extended from s[i..j] (inclusive) by expanding around the center\nfunction expandAroundCenter(s, i, j) {\n // Expand the palindrome by moving outward from the center while the characters match\n while (i >= 0 && j < s.length && s[i] === s[j]) {\n i--; // Move the left index to the left\n j++; // Move the right index to the right\n }\n // Return the indices of the longest palindrome found\n return [i + 1, j - 1];\n}\n\n```\n``` C# []\npublic class Solution {\n public string LongestPalindrome(string s) {\n // Check if the input string is empty, return an empty string if so\n if (string.IsNullOrEmpty(s))\n return "";\n\n // Initialize variables to store the indices of the longest palindrome found\n int[] longestPalindromeIndices = { 0, 0 };\n\n // Loop through the characters in the input string\n for (int i = 0; i < s.Length; ++i) {\n // Find the indices of the longest palindrome centered at character i\n int[] currentIndices = ExpandAroundCenter(s, i, i);\n\n // Compare the length of the current palindrome with the longest found so far\n if (currentIndices[1] - currentIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the current one is longer\n longestPalindromeIndices = currentIndices;\n }\n\n // Check if there is a possibility of an even-length palindrome centered at\n // character i and i+1\n if (i + 1 < s.Length && s[i] == s[i + 1]) {\n // Find the indices of the longest even-length palindrome centered at characters\n // i and i+1\n int[] evenIndices = ExpandAroundCenter(s, i, i + 1);\n\n // Compare the length of the even-length palindrome with the longest found so\n // far\n if (evenIndices[1] - evenIndices[0] > longestPalindromeIndices[1] - longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the even-length one is longer\n longestPalindromeIndices = evenIndices;\n }\n }\n }\n\n // Extract and return the longest palindrome substring using the indices\n return s.Substring(longestPalindromeIndices[0], longestPalindromeIndices[1] - longestPalindromeIndices[0] + 1);\n }\n\n // Helper function to find and return the indices of the longest palindrome\n // extended from s[i..j] (inclusive) by expanding around the center\n private int[] ExpandAroundCenter(string s, int i, int j) {\n // Expand the palindrome by moving outward from the center while the characters match\n while (i >= 0 && j < s.Length && s[i] == s[j]) {\n i--; // Move the left index to the left\n j++; // Move the right index to the right\n }\n // Return the indices of the longest palindrome found\n return new int[] { i + 1, j - 1 };\n }\n}\n```\n``` PHP []\nclass Solution {\n public function longestPalindrome($s) {\n // Check if the input string is empty, return an empty string if so\n if (empty($s)) {\n return "";\n }\n\n // Initialize variables to store the indices of the longest palindrome found\n $longestPalindromeIndices = array(0, 0);\n\n // Loop through the characters in the input string\n for ($i = 0; $i < strlen($s); ++$i) {\n // Find the indices of the longest palindrome centered at character i\n $currentIndices = $this->expandAroundCenter($s, $i, $i);\n\n // Compare the length of the current palindrome with the longest found so far\n if ($currentIndices[1] - $currentIndices[0] > $longestPalindromeIndices[1] - $longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the current one is longer\n $longestPalindromeIndices = $currentIndices;\n }\n\n // Check if there is a possibility of an even-length palindrome centered at\n // character i and i+1\n if ($i + 1 < strlen($s) && $s[$i] == $s[$i + 1]) {\n // Find the indices of the longest even-length palindrome centered at characters\n // i and i+1\n $evenIndices = $this->expandAroundCenter($s, $i, $i + 1);\n\n // Compare the length of the even-length palindrome with the longest found so\n // far\n if ($evenIndices[1] - $evenIndices[0] > $longestPalindromeIndices[1] - $longestPalindromeIndices[0]) {\n // Update the longest palindrome indices if the even-length one is longer\n $longestPalindromeIndices = $evenIndices;\n }\n }\n }\n\n // Extract and return the longest palindrome substring using the indices\n return substr($s, $longestPalindromeIndices[0], $longestPalindromeIndices[1] - $longestPalindromeIndices[0] + 1);\n }\n\n // Helper function to find and return the indices of the longest palindrome\n // extended from s[i..j] (inclusive) by expanding around the center\n private function expandAroundCenter($s, $i, $j) {\n // Expand the palindrome by moving outward from the center while the characters match\n while ($i >= 0 && $j < strlen($s) && $s[$i] == $s[$j]) {\n $i--; // Move the left index to the left\n $j++; // Move the right index to the right\n }\n // Return the indices of the longest palindrome found\n return array($i + 1, $j - 1);\n }\n}\n```\n![vote.jpg](https://assets.leetcode.com/users/images/6abbd7cf-6e46-4efe-ab50-c5ebc2bdc632_1698374053.3694885.jpeg)\n\n---\n\n# 2nd Method :- Manacher\'s Algorithm \uD83D\uDEA9\n\n## Intuition \uD83D\uDE80:\nThe code implements Manacher\'s algorithm, which is designed to find the longest palindromic substring in a given string. The algorithm is an efficient way to tackle this problem and is based on the following key ideas:\n\n1. Utilize symmetry: Palindromes have a property of symmetry, which means their left and right sides are mirror images of each other. Manacher\'s algorithm takes advantage of this property to optimize the process.\n\n2. Avoid redundant computations: The algorithm uses previously computed information to avoid redundant checks, which makes it more efficient than brute force methods.\n\n## Approach \uD83D\uDE80:\n\n1. **Preprocessing**:\n - The input string `s` is preprocessed to create a modified string `T` with special characters (^, #, and dollar ) inserted between each character to simplify palindrome detection.\n\n2. **Initialization**:\n - Initialize variables:\n - `strLength` for the length of the modified string `T`.\n - `palindromeLengths`, an array to store the lengths of palindromes centered at each position in `T`.\n - `center` for the current center of the palindrome being processed.\n - `rightEdge` for the rightmost edge of the palindrome found so far.\n\n3. **Palindrome Detection**:\n - Loop through the modified string `T` to find palindromes centered at each position.\n - Calculate the length of the palindrome at the current position `i` based on previously computed information and expand it if possible. This is done by comparing characters around the current position.\n - Update `center` and `rightEdge` if a longer palindrome is found.\n\n4. **Find the Longest Palindrome**:\n - After processing the entire modified string `T`, identify the longest palindrome by searching the `palindromeLengths` array for the maximum value.\n - Determine the center of this longest palindrome.\n\n5. **Extract the Result**:\n - Use the information about the longest palindrome (center and length) in the modified string `T` to extract the corresponding substring from the original input string `s`.\n\nThe code effectively implements this approach to find and return the longest palindromic substring in the input string `s`. Manacher\'s algorithm is more efficient than naive methods because it takes advantage of the properties of palindromes and avoids redundant comparisons, making it a good choice for solving this problem.\n\n\n## Complexity \uD83D\uDE81\n### \uD83C\uDFF9 Time complexity: O(N)\nThe time complexity of Manacher\'s algorithm is O(N), where N is the length of the input string `s`. This is because the algorithm processes each character of the modified string exactly once (with some constant factor overhead) in a linear pass. The key factor in achieving this efficiency is the "center expansion" technique used to find palindromes, which avoids unnecessary character comparisons. \n\n### \uD83C\uDFF9 Space complexity: O(N)\nThe space complexity of the code is O(N) as well. This is primarily due to the creation of the modified string `T`, which is constructed by adding extra characters, such as \'^\', \'#\', and \'$\', to the original string. The `P` array used to store the lengths of palindromes at each position also has a space complexity of O(N) because it is an array of the same length as the modified string. The other variables used in the algorithm (e.g., `C`, `R`, and loop counters) have constant space requirements and do not significantly contribute to the space complexity.\n\nSo, in terms of both time and space complexity, this code is very efficient for finding the longest palindromic substring in a string.\n\n\n## Code \u2712\uFE0F\n``` Java []\npublic class Solution {\n public String longestPalindrome(String s) {\n // Step 1: Preprocess the input string\n StringBuilder processedStr = new StringBuilder("^#");\n for (char c : s.toCharArray()) {\n processedStr.append(c).append("#");\n }\n processedStr.append("$");\n String modifiedString = processedStr.toString();\n\n // Step 2: Initialize variables for the algorithm\n int strLength = modifiedString.length();\n int[] palindromeLengths = new int[strLength];\n int center = 0; // Current center of the palindrome\n int rightEdge = 0; // Rightmost edge of the palindrome\n\n // Step 3: Loop through the modified string to find palindromes\n for (int i = 1; i < strLength - 1; i++) {\n palindromeLengths[i] = (rightEdge > i) ? Math.min(rightEdge - i, palindromeLengths[2 * center - i]) : 0;\n \n // Expand the palindrome around the current character\n while (modifiedString.charAt(i + 1 + palindromeLengths[i]) == modifiedString.charAt(i - 1 - palindromeLengths[i])) {\n palindromeLengths[i]++;\n }\n \n // Update the rightmost edge and center if necessary\n if (i + palindromeLengths[i] > rightEdge) {\n center = i;\n rightEdge = i + palindromeLengths[i];\n }\n }\n\n // Step 4: Find the longest palindrome and its center\n int maxLength = 0;\n int maxCenter = 0;\n for (int i = 0; i < strLength; i++) {\n if (palindromeLengths[i] > maxLength) {\n maxLength = palindromeLengths[i];\n maxCenter = i;\n }\n }\n \n // Step 5: Extract the longest palindrome from the modified string\n int start = (maxCenter - maxLength) / 2;\n int end = start + maxLength;\n\n // Return the longest palindrome in the original string\n return s.substring(start, end);\n }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n std::string longestPalindrome(std::string s) {\n // Step 1: Preprocess the input string\n std::string processedStr = "^#";\n for (char c : s) {\n processedStr.push_back(c);\n processedStr.push_back(\'#\');\n }\n processedStr.push_back(\'$\');\n\n // Step 2: Initialize variables for the algorithm\n int strLength = processedStr.length();\n std::vector palindromeLengths(strLength, 0);\n int center = 0; // Current center of the palindrome\n int rightEdge = 0; // Rightmost edge of the palindrome\n\n // Step 3: Loop through the modified string to find palindromes\n for (int i = 1; i < strLength - 1; i++) {\n palindromeLengths[i] = (rightEdge > i) ? std::min(rightEdge - i, palindromeLengths[2 * center - i]) : 0;\n\n // Expand the palindrome around the current character\n while (processedStr[i + 1 + palindromeLengths[i]] == processedStr[i - 1 - palindromeLengths[i]]) {\n palindromeLengths[i]++;\n }\n\n // Update the rightmost edge and center if necessary\n if (i + palindromeLengths[i] > rightEdge) {\n center = i;\n rightEdge = i + palindromeLengths[i];\n }\n }\n\n // Step 4: Find the longest palindrome and its center\n int maxLength = 0;\n int maxCenter = 0;\n for (int i = 0; i < strLength; i++) {\n if (palindromeLengths[i] > maxLength) {\n maxLength = palindromeLengths[i];\n maxCenter = i;\n }\n }\n\n // Step 5: Extract the longest palindrome from the modified string\n int start = (maxCenter - maxLength) / 2;\n int end = start + maxLength;\n\n // Return the longest palindrome in the original string\n return s.substr(start, end - start);\n }\n};\n```\n``` Python []\nclass Solution:\n def longestPalindrome(self, s: str) -> str:\n # Step 1: Preprocess the input string\n processed_str = "^#"\n for c in s:\n processed_str += c + "#"\n processed_str += "$"\n\n # Step 2: Initialize variables for the algorithm\n str_length = len(processed_str)\n palindrome_lengths = [0] * str_length\n center = 0 # Current center of the palindrome\n right_edge = 0 # Rightmost edge of the palindrome\n\n # Step 3: Loop through the modified string to find palindromes\n for i in range(1, str_length - 1):\n palindrome_lengths[i] = min(right_edge - i, palindrome_lengths[2 * center - i]) if right_edge > i else 0\n\n # Expand the palindrome around the current character\n while processed_str[i + 1 + palindrome_lengths[i]] == processed_str[i - 1 - palindrome_lengths[i]]:\n palindrome_lengths[i] += 1\n\n # Update the rightmost edge and center if necessary\n if i + palindrome_lengths[i] > right_edge:\n center = i\n right_edge = i + palindrome_lengths[i]\n\n # Step 4: Find the longest palindrome and its center\n max_length = 0\n max_center = 0\n for i in range(str_length):\n if palindrome_lengths[i] > max_length:\n max_length = palindrome_lengths[i]\n max_center = i\n\n # Step 5: Extract the longest palindrome from the modified string\n start = (max_center - max_length) // 2\n end = start + max_length\n\n # Return the longest palindrome in the original string\n return s[start:end]\n```\n``` JavaScript []\nclass Solution {\n longestPalindrome(s) {\n // Step 1: Preprocess the input string\n let processedStr = "^#";\n for (let i = 0; i < s.length; i++) {\n processedStr += s[i] + "#";\n }\n processedStr += "$";\n let modifiedString = processedStr;\n\n // Step 2: Initialize variables for the algorithm\n let strLength = modifiedString.length;\n let palindromeLengths = new Array(strLength).fill(0);\n let center = 0; // Current center of the palindrome\n let rightEdge = 0; // Rightmost edge of the palindrome\n\n // Step 3: Loop through the modified string to find palindromes\n for (let i = 1; i < strLength - 1; i++) {\n palindromeLengths[i] = (rightEdge > i) ? Math.min(rightEdge - i, palindromeLengths[2 * center - i]) : 0;\n\n // Expand the palindrome around the current character\n while (modifiedString[i + 1 + palindromeLengths[i]] === modifiedString[i - 1 - palindromeLengths[i]]) {\n palindromeLengths[i]++;\n }\n\n // Update the rightmost edge and center if necessary\n if (i + palindromeLengths[i] > rightEdge) {\n center = i;\n rightEdge = i + palindromeLengths[i];\n }\n }\n\n // Step 4: Find the longest palindrome and its center\n let maxLength = 0;\n let maxCenter = 0;\n for (let i = 0; i < strLength; i++) {\n if (palindromeLengths[i] > maxLength) {\n maxLength = palindromeLengths[i];\n maxCenter = i;\n }\n }\n\n // Step 5: Extract the longest palindrome from the modified string\n let start = (maxCenter - maxLength) / 2;\n let end = start + maxLength;\n\n // Return the longest palindrome in the original string\n return s.substring(start, end);\n }\n}\n```\n``` C# []\npublic class Solution {\n public string LongestPalindrome(string s) {\n // Step 1: Preprocess the input string\n StringBuilder processedStr = new StringBuilder("^#");\n foreach (char c in s) {\n processedStr.Append(c).Append("#");\n }\n processedStr.Append("$");\n string modifiedString = processedStr.ToString();\n\n // Step 2: Initialize variables for the algorithm\n int strLength = modifiedString.Length;\n int[] palindromeLengths = new int[strLength];\n int center = 0; // Current center of the palindrome\n int rightEdge = 0; // Rightmost edge of the palindrome\n\n // Step 3: Loop through the modified string to find palindromes\n for (int i = 1; i < strLength - 1; i++) {\n palindromeLengths[i] = (rightEdge > i) ? Math.Min(rightEdge - i, palindromeLengths[2 * center - i]) : 0;\n\n // Expand the palindrome around the current character\n while (modifiedString[i + 1 + palindromeLengths[i]] == modifiedString[i - 1 - palindromeLengths[i]]) {\n palindromeLengths[i]++;\n }\n\n // Update the rightmost edge and center if necessary\n if (i + palindromeLengths[i] > rightEdge) {\n center = i;\n rightEdge = i + palindromeLengths[i];\n }\n }\n\n // Step 4: Find the longest palindrome and its center\n int maxLength = 0;\n int maxCenter = 0;\n for (int i = 0; i < strLength; i++) {\n if (palindromeLengths[i] > maxLength) {\n maxLength = palindromeLengths[i];\n maxCenter = i;\n }\n }\n\n // Step 5: Extract the longest palindrome from the modified string\n int start = (maxCenter - maxLength) / 2;\n int end = start + maxLength;\n\n // Return the longest palindrome in the original string\n return s.Substring(start, end - start);\n }\n}\n```\n``` PHP []\nclass Solution {\n public function longestPalindrome($s) {\n // Step 1: Preprocess the input string\n $processedStr = "^#";\n for ($i = 0; $i < strlen($s); $i++) {\n $processedStr .= $s[$i] . "#";\n }\n $processedStr .= "$";\n $modifiedString = $processedStr;\n\n // Step 2: Initialize variables for the algorithm\n $strLength = strlen($modifiedString);\n $palindromeLengths = array_fill(0, $strLength, 0);\n $center = 0; // Current center of the palindrome\n $rightEdge = 0; // Rightmost edge of the palindrome\n\n // Step 3: Loop through the modified string to find palindromes\n for ($i = 1; $i < $strLength - 1; $i++) {\n $palindromeLengths[$i] = ($rightEdge > $i) ? min($rightEdge - $i, $palindromeLengths[2 * $center - $i]) : 0;\n\n // Expand the palindrome around the current character\n while ($modifiedString[$i + 1 + $palindromeLengths[$i]] == $modifiedString[$i - 1 - $palindromeLengths[$i]]) {\n $palindromeLengths[$i]++;\n }\n\n // Update the rightmost edge and center if necessary\n if ($i + $palindromeLengths[$i] > $rightEdge) {\n $center = $i;\n $rightEdge = $i + $palindromeLengths[$i];\n }\n }\n\n // Step 4: Find the longest palindrome and its center\n $maxLength = 0;\n $maxCenter = 0;\n for ($i = 0; $i < $strLength; $i++) {\n if ($palindromeLengths[$i] > $maxLength) {\n $maxLength = $palindromeLengths[$i];\n $maxCenter = $i;\n }\n }\n\n // Step 5: Extract the longest palindrome from the modified string\n $start = ($maxCenter - $maxLength) / 2;\n $end = $start + $maxLength;\n\n // Return the longest palindrome in the original string\n return substr($s, $start, $end - $start);\n }\n}\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/d2f2c9af-7fdd-4731-8b22-edd260e4d466_1698374064.625327.png)\n# Up Vote Guys\n

Longest Palindromic Substring

Problem Description

Problem Description

Answer Panel