C Language Algorithm – Longest Palindromic Substring

Today's algorithm problem is to solve the "Longest Palindromic Substring" problem using C language. Below are my algorithm ideas and implementation. Let's take a look.

Algorithm Problem
Given a string, find the longest palindromic substring within it.

Algorithm Idea
We will use the center expansion algorithm to solve the longest palindromic substring problem. The idea is to traverse each character in the string and expand outwards from that character to find the longest palindromic substring centered at it. We also need to consider both odd and even lengths of palindromic substrings.

The steps of the algorithm are as follows:
1. Define a function <strong>expandFromCenter</strong> that takes the given string and a center index as parameters, and returns the length of the longest palindromic substring centered at that index.
2. Define a function <strong>longestPalindrome</strong> that takes the given string as a parameter and returns the longest palindromic substring.
3. In the <strong>longestPalindrome</strong> function, traverse each character in the string.
4. For each character, call the <strong>expandFromCenter</strong> function to handle both odd and even length palindromes.
5. Compare the lengths of the obtained palindromic substrings and update the start and end indices of the longest palindromic substring.
6. Extract the substring based on the start and end indices of the longest palindromic substring and return it.

Code Implementation
Below is an example code implementing the "Longest Palindromic Substring" algorithm in C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int expandFromCenter(char *s, int left, int right) {
    while (left >= 0 && right < strlen(s) && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

char* longestPalindrome(char *s) {
    if (s == NULL || strlen(s) < 1)
        return "";
    int start = 0, end = 0;
    for (int i = 0; i < strlen(s); i++) {
        int len1 = expandFromCenter(s, i, i);      // Handle odd length palindromes
        int len2 = expandFromCenter(s, i, i + 1);  // Handle even length palindromes
        int len = len1 > len2 ? len1 : len2;
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    char *result = malloc(sizeof(char) * (end - start + 2));
    strncpy(result, s + start, end - start + 1);
    result[end - start + 1] = '\0';
    return result;
}

int main() {
    char input[] = "babad";
    char *result = longestPalindrome(input);
    printf("Input: %s\n", input);
    printf("Longest Palindrome: %s\n", result);
    free(result);
    return 0;
}

Algorithm Analysis
The time complexity of this algorithm is <strong>O(n^2</strong>), where n is the length of the string. This is because we need to traverse each character in the string and expand from each character.
The space complexity is <strong>O(1</strong>, as we do not use extra space apart from storing the result.

Examples and Testing
Example Input 1:
"babad"
Example Output 1:
Longest Palindrome: "bab"
Example Input 2:
"cbbd"
Example Output 2:
Longest Palindrome: "bb"

Conclusion
This article presents the code to solve the longest palindromic substring problem using C language. By using the center expansion algorithm, we can effectively find the longest palindromic substring in the given string. This problem is a classic problem in string processing, and solving it requires attention to both odd and even lengths of palindromic substrings. The time complexity of the algorithm is <strong>O(n^2</strong>, and the space complexity is <strong>O(1)</strong>.