Longest Palindromic Substring

class Solution {
public:
    string findLongestPalindrome(string str) {
        string modifiedString = "#";
        for (char ch : str) {
            modifiedString += ch;
            modifiedString += "#";
        }

        int strLength = modifiedString.length();
        vector<int> radii(strLength, 0);
        int C = 0;
        int R = 0;

        for (int i = 0; i < strLength; i++) {
            int mirror = 2 * C - i;

            if (i < R) {
                radii[i] = min(R - i, radii[mirror]);
            }

            while (i + 1 + radii[i] < strLength &&
                   i - 1 - radii[i] >= 0 &&
                   modifiedString[i + 1 + radii[i]] ==
                       modifiedString[i - 1 - radii[i]]) {
                radii[i]++;
            }

            if (i + radii[i] > R) {
                C = i;
                R = i + radii[i];
            }
        }

        int longestLength = 0;
        int bestCenter = 0;
        for (int i = 0; i < strLength; i++) {
            if (radii[i] > longestLength) {
                longestLength = radii[i];
                bestCenter = i;
            }
        }

        int startIndex = (bestCenter - longestLength) / 2;
        string longest_substring = str.substr(startIndex, longestLength);

        return longest_substring;
    }
};

The given C++ code implements a solution to find the longest palindromic substring within a given string. The approach used in this solution involves expanding from the center and modifying the string by placing a "#" between each character as well as at the beginning and end. This technique converts the string so that palindrome checks for even length can be done in the same way as for odd length.

Here’s a concise breakdown of the algorithm used:

• Insert a "#" character between each character of the input string and also at the beginning and end. This transformation handles the unified approach for finding palindromes of both odd and even lengths.
• Initialize an array radii where radii[i] represents the radius of the palindrome centered at i in the modified string including the center character itself.
• Use two pointers, C (center of the current rightmost palindrome) and R (right boundary of this palindrome), to track the farthest reached palindrome.
• Iterate through each character of the modified string:
  • Calculate the mirror index of the current character based on the center C.
  • Use previously known palindromic radii values from the radii array to avoid unnecessary recalculations.
  • Attempt to expand the palindrome centered at each character until the conditions (staying within bounds and characters matching on both sides) are met.
  • If expanding this palindrome goes beyond the current known right boundary (R), update C and R.
• After the main loop, determine the longest palindrome by finding the max value in the radii array.
• Translate the index and length from the modified string back to indexes suitable for the original unmodified string.

Ultimately, the function extracts the substring of the original string which represents the longest palindrome and returns it. This implementation efficiently finds the longest palindromic substring in linear time relative to the size of the input string.

class Solution {
    public String findLongestPalindrome(String input) {
        StringBuilder modifiedString = new StringBuilder("#");
        for (char c : input.toCharArray()) {
            modifiedString.append(c).append("#");
        }

        int length = modifiedString.length();
        int[] radii = new int[length];
        int currentCenter = 0;
        int currentRadius = 0;

        for (int i = 0; i < length; i++) {
            int reflectedIndex = 2 * currentCenter - i;

            if (i < currentRadius) {
                radii[i] = Math.min(
                    currentRadius - i,
                    radii[reflectedIndex]
                );
            }

            while (
                i + 1 + radii[i] < length &&
                i - 1 - radii[i] >= 0 &&
                modifiedString.charAt(i + 1 + radii[i]) ==
                    modifiedString.charAt(i - 1 - radii[i])
            ) {
                radii[i]++;
            }

            if (i + radii[i] > currentRadius) {
                currentCenter = i;
                currentRadius = i + radii[i];
            }
        }

        int maxLen = 0;
        int centerIdx = 0;
        for (int i = 0; i < length; i++) {
            if (radii[i] > maxLen) {
                maxLen = radii[i];
                centerIdx = i;
            }
        }

        int startIdx = (centerIdx - maxLen) / 2;
        String result = input.substring(
            startIdx,
            startIdx + maxLen
        );

        return result;
    }
}

In the provided Java solution for finding the longest palindromic substring, the code uses the Manacher's algorithm, which is efficient for this problem with a linear time complexity. Below is a breakdown of how the solution works:

• Start by transforming the original input string to include '#' characters between each character. This modification helps handle palindromes of even length uniformly with those of odd length.

• Initiate an array radii to store the radius of the longest palindrome at each character in the modified string.

• As iteration through the modifiedString progresses, check if the current character can mirror the palindrome properties of the character at a reflected position from a known center currentCenter. Adjust the radius for this character based on comparisons.

• For each character, extend the radius of the palindrome as far as symmetry holds on both sides.

• Update the currentCenter and currentRadius if the palindrome extends beyond the previously known bounds.

• After the main loop, determine the longest palindrome by scanning through the radii array and calculate the starting index of this palindrome in the original input string by adjusting for the added '#' characters.

• Finally, extract the longest palindromic substring using this start index and the length from the radii array.

This concise algorithm effectively finds the longest palindromic substring in a given string by cleverly utilizing character mirroring and dynamic center shifting, ensuring the processing time remains linear with respect to the input size. This is significantly more efficient than simpler quadratic or cubic solutions.

#include "stdlib.h"
#include "string.h"

char* findLongestPalindromeSubstr(char* input_string) {
    int length = strlen(input_string);
    char* modified_string = (char*)malloc(sizeof(char) * (2 * length + 2));
    modified_string[0] = '#';
    int position = 1;
    for (int idx = 0; idx < length; idx++) {
        modified_string[position++] = input_string[idx];
        modified_string[position++] = '#';
    }
    modified_string[position] = '\0';

    int n = strlen(modified_string);
    int* radii = (int*)malloc(n * sizeof(int));
    memset(radii, 0, n * sizeof(int));
    int center_pos = 0;
    int current_radius = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * center_pos - i;

        if (i < current_radius) {
            radii[i] = (current_radius - i > radii[mirror]
                                       ? radii[mirror]
                                       : current_radius - i);
        }

        while (i + 1 + radii[i] < n &&
               i - 1 - radii[i] >= 0 &&
               modified_string[i + 1 + radii[i]] ==
                   modified_string[i - 1 - radii[i]]) {
            radii[i]++;
        }

        if (i + radii[i] > current_radius) {
            center_pos = i;
            current_radius = i + radii[i];
        }
    }

    int max_length = 0;
    int optimal_center = 0;
    for (int i = 0; i < n; i++) {
        if (radii[i] > max_length) {
            max_length = radii[i];
            optimal_center = i;
        }
    }

    int initial_index = (optimal_center - max_length) / 2;
    char* result_palindrome = (char*)malloc(max_length + 1);
    strncpy(result_palindrome, &input_string[initial_index], max_length);
    result_palindrome[max_length] = '\0';

    free(modified_string);
    free(radii);

    return result_palindrome;
}

The provided C code implements a function to find the longest palindromic substring in a given string. The approach used is an optimized version that utilizes the Manacher's Algorithm that effectively reduces the complexity of finding the longest palindrome. Here's a brief breakdown of key operations:

• First, transform the input string by inserting a # character between each character and at the ends. This helps in handling even-length palindromes uniformly with odd-length ones.
• Initialize arrays to keep track of the current longest radii of palindromes for each character in the transformed string.
• Use a center expansion technique where for each character in the modified string, expand around that character to find palindromes, while keeping track of the longest palindrome found.
• Update the center and the right boundary of the palindrome whenever the expanded palindrome surpasses the current known boundaries.
• Scan through the array of radii to determine the maximum length of the palindrome and its central position.
• Extract the longest palindromic substring from the original input string using indices computed from the modified string's center and radius information.
• Memory management is handled explicitly using malloc and free to allocate and deallocate memory used by helper data structures.

The implementation ensures efficient memory usage and processing, handling cases to compute the longest palindromic substring in linear time, which is well-suited for large input strings.

var findLongestPalindrome = function (stringInput) {
    let transformedString = "#";
    for (let character of stringInput) {
        transformedString += character;
        transformedString += "#";
    }

    let lengthOfTransformed = transformedString.length;
    let radiusArray = new Array(lengthOfTransformed).fill(0);
    let currentCenter = 0;
    let currentRadius = 0;

    for (let index = 0; index < lengthOfTransformed; index++) {
        let mirroredIndex = 2 * currentCenter - index;

        if (index < currentRadius)
            radiusArray[index] = Math.min(currentRadius - index, radiusArray[mirroredIndex]);

        while (
            index + 1 + radiusArray[index] < lengthOfTransformed &&
            index - 1 - radiusArray[index] >= 0 &&
            transformedString.charAt(index + 1 + radiusArray[index]) ==
                transformedString.charAt(index - 1 - radiusArray[index])
        )
            radiusArray[index]++;

        if (index + radiusArray[index] > currentRadius) {
            currentCenter = index;
            currentRadius = index + radiusArray[index];
        }
    }

    let maxRadius = 0;
    let indexAtMaxRadius = 0;
    for (let i = 0; i < lengthOfTransformed; i++) {
        if (radiusArray[i] > maxRadius) {
            maxRadius = radiusArray[i];
            indexAtMaxRadius = i;
        }
    }

    let startOfLongestPalindrome = Math.floor((indexAtMaxRadius - maxRadius) / 2);
    let resultLongestPalindrome = stringInput.slice(startOfLongestPalindrome, startOfLongestPalindrome + maxRadius);

    return resultLongestPalindrome;
};

The JavaScript function findLongestPalindrome effectively computes the longest palindromic substring found within a given string. The process leverages a transformative approach that involves working with an augmented version of the original string, facilitating a straightforward palindrome detection.

• The initial step introduces symbols between characters and at the extremities of the input string. This conversion ensures that palindromes of both even and odd lengths can be uniformly handled as odd-length palindromes.
• An array radiusArray is utilized to store the maximum radius of parity from each position in the transformed string during the exploration.
• Central variables, currentCenter and currentRadius, are adjusted dynamically with each expansion to efficiently manage and keep track of the current palindrome's center and boundaries.
• A mirrored calculation strategy helps optimize each radius expansion by reusing previously calculated results, hence speeding up the process.
• After successfully identifying potential centers and their corresponding radii, the function detects the longest palindrome by selecting the maximum value in radiusArray.
• The start index of the substring in the original input string is recalculated without the added characters, and the actual longest palindrome is extracted and returned.

This function provides an efficient solution to the palindrome identification problem by leveraging a modified string and radius expansion technique to handle substrings systematically. It offers a complexity that is generally more manageable compared to simplistic brute force approaches.

class Solution:
    def findLongestPalindrome(self, input_string: str) -> str:
        modified_string = "#" + "#".join(input_string) + "#"
        length = len(modified_string)
        palindrome_lengths = [0] * length
        current_center = current_radius = 0

        for i in range(length):
            reflection = 2 * current_center - i

            if i < current_radius:
                palindrome_lengths[i] = min(current_radius - i, palindrome_lengths[reflection])

            while (
                i + 1 + palindrome_lengths[i] < length
                and i - 1 - palindrome_lengths[i] >= 0
                and modified_string[i + 1 + palindrome_lengths[i]]
                == modified_string[i - 1 - palindrome_lengths[i]]
            ):
                palindrome_lengths[i] += 1

            if i + palindrome_lengths[i] > current_radius:
                current_center = i
                current_radius = i + palindrome_lengths[i]

        max_len = max(palindrome_lengths)
        center_pos = palindrome_lengths.index(max_len)
        initial_pos = (center_pos - max_len) // 2
        result_palindrome = input_string[initial_pos : initial_pos + max_len]

        return result_palindrome

The provided Python code defines a solution for finding the longest palindromic substring within a given string. The method findLongestPalindrome efficiently determines the longest sequence of characters that reads the same forwards and backwards. Here's a concise overview of how the algorithm functions:

• Initialize a modified version of the input string to include hash (#) characters. These act as boundaries, preventing index overflow and aiding in center expansion checks.
• Create and populate an array to track the lengths of potential palindromes around each character (or hash) in the modified string.
• Use two pointers, current_center and current_radius, to hold the center and the radius (length) of the current known largest palindrome.
• Utilize the characteristics of palindromes around the center to efficiently calculate possible palindromic lengths.
  • If the current index is within the radius of the current largest palindrome, utilize its symmetric property.
  • Expand the palindrome from the current center outwards, checking for matching characters.
  • Update the current_center and current_radius if the newly found palindrome is larger.
• After traversing the string, identify the maximum palindrome length and its position.
• Extract and return the longest palindromic substring from the original input string based on calculations from the modified string.

This algorithm leverages symmetrical properties of palindromes to enhance efficiency, avoiding the naive approach which requires checking each substring one by one. The user of this code can thus expect a function optimized for faster execution and lower computational overhead when determining palindromic sequences.