Palindrome Radius:

For every position in the string, we calculate the radius of the palindrome centred at that position.

Optimised Expansion:

Instead of expanding at every character independently, we leverage the symmetry of palindromes and use previously computed results.

Approach

Preprocessing:
- Transform the input string s by inserting special characters:
  - Original: "babad"
  - Transformed: "#b#a#b#a#d#"
- This ensures all palindromes are odd-length, simplifying calculations.
Initialisation:
- Create an auxiliary array p where p[i] stores the radius of the palindrome centred at position i.
- Maintain two key variables:
  - center: The centre of the palindrome currently being expanded.
  - right: The right boundary (exclusive) of this palindrome.
Iterative Expansion:
- For each index i in the transformed string:
  - If i falls within the current palindrome (i < right), mirror the palindrome radius at the symmetric point (mirror = 2*center - i) to initialise p[i].
  - Expand around i outward while the left and right characters match.
  - Update center and right if the newly expanded palindrome extends beyond the current right boundary.
Post-Processing:
- The longest palindrome in the original string corresponds to the maximum radius in the p array.

Code

[{"language":"Java","code":"class Solution {\n    public String longestPalindrome(String s) {\n        // Step 1: Preprocess the string\n        StringBuilder sb = new StringBuilder();\n        sb.append(\"#\"); // Add boundary character to simplify palindrome handling\n        for (char c : s.toCharArray()) {\n            sb.append(c);\n            sb.append(\"#\");\n        }\n        String transformed = sb.toString();\n        int n = transformed.length(); \n        \n        // Step 2: Initialise auxiliary array\n        int[] p = new int[n]; // Array to track palindrome radii\n        int center = 0, right = 0; // Current center and right boundary of palindrome\n\n        // Step 3: Expand around each character\n        for (int i = 0; i < n; i++) {\n            int mirror = 2 * center - i; // Mirrored index for `i`\n            if (i < right) {\n                p[i] = Math.min(p[mirror], right - i); // Initialise radius\n            }\n            \n            // Try to expand the palindrome centered at `i`\n            int a = i + p[i] + 1;\n            int b = i - p[i] - 1;\n            while (a < n && b >= 0 && transformed.charAt(a) == transformed.charAt(b)) {\n                p[i]++;\n                a++;\n                b--;\n            }\n            \n            // Update center and right boundary if palindrome expands beyond right\n            if (i + p[i] > right) {\n                center = i;\n                right = i + p[i];\n            }\n        }\n\n        // Step 4: Find the longest palindrome\n        int maxLen = 0, start = 0;\n        for (int i = 0; i < n; i++) {\n            if (p[i] > maxLen) {\n                maxLen = p[i];\n                start = (i - maxLen) / 2; // Map back to original string\n            }\n        }\n\n        return s.substring(start, start + maxLen);\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def longestPalindrome(self, s: str) -> str:\n        # Step 1: Preprocess the string\n        transformed = \"#\".join(f\"#{s}#\")\n        n = len(transformed)\n        \n        #

Related Tags