Find Longest Palindromic Substring in C, C++, Java, and Python

Introduction

In this article, we will explore different programming languages, including C, C++, Java, and Python, to find the longest palindromic substring.

A palindromic substring is a sequence of characters that reads the same forward and backward.

Also Read: Longest Subarray of 1’s After Deleting One Element

Finding the longest palindromic substring is a common problem in string manipulation and is often encountered in various programming tasks.

By understanding the techniques and algorithms used in different programming languages, you will be able to solve this problem efficiently and enhance your programming skills.

Program to Find Longest Palindromic Substring in C

Implementation in C

To find the longest palindromic substring in C, we can use the brute-force approach or implement more optimized algorithms such as Manacher’s algorithm.

Also Read: Median of Two Sorted Arrays in C, C++, Java and Python

Here is a sample implementation of finding the longest palindromic substring in C using the brute-force approach:

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

int isPalindrome(char str[], int start, int end) {
    while (start < end) {
        if (str[start] != str[end])
            return 0;
        start++;
        end--;
    }
    return 1;
}

void findLongestPalindrome(char str[]) {
    int len = strlen(str);
    int maxLength = 1;
    int start = 0;

    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            if (isPalindrome(str, i, j) && (j - i + 1) > maxLength) {
                maxLength = j - i + 1;
                start = i;
            }
        }
    }

    printf("Longest palindromic substring: ");
    for (int i = start; i < start + maxLength; i++) {
        printf("%c", str[i]);
    }
    printf("\n");
}

int main() {
    char str[] = "babad";
    findLongestPalindrome(str);
    return 0;
}

Explanation

In the given C program, we first define a helper function isPalindrome that checks whether a substring is a palindrome or not.

It takes the string, start index, and end index as input and iteratively compares the characters from both ends. If the characters mismatch, it returns 0; otherwise, it returns 1.

Also Read: Longest Substring Without Repeating Characters

The findLongestPalindrome function iterates through all possible substrings and checks if each substring is a palindrome.

It keeps track of the maximum length and the starting index of the longest palindromic substring found so far. Finally, it prints the longest palindromic substring.

The main function demonstrates the usage of the findLongestPalindrome function by providing a sample string “babad” as input.

Program to Find Longest Palindromic Substring in C++

Implementation in C++

C++ offers a more object-oriented approach to programming and provides libraries and data structures that can be utilized to solve complex problems efficiently.

Also Read: Two Sum in C Programming with Solution: A Comprehensive Guide

Here is an implementation of finding the longest palindromic substring in C++ using dynamic programming:

#include <iostream>
#include <vector>

std::string findLongestPalindrome(const std::string& str) {
    int n = str.length();
    std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));

    int maxLength = 1;
    int start = 0;

    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        if (i < n - 1 && str[i] == str[i + 1]) {
            dp[i][i + 1] = true;
            maxLength = 2;
            start = i;
        }
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (str[i] == str[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                maxLength = len;
                start = i;
            }
        }
    }

    return str.substr(start, maxLength);
}

int main() {
    std::string str = "babad";
    std::string longestPalindrome = findLongestPalindrome(str);
    std::cout << "Longest palindromic substring: " << longestPalindrome << std::endl;
    return 0;
}

Explanation

In the given C++ program, we utilize dynamic programming to solve the problem of finding the longest palindromic substring.

We define a 2D boolean array dp of size n x n, where dp[i][j] indicates whether the substring from index i to index j is a palindrome or not.

Also Read: Getchar and Putchar in C: A Comprehensive Guide

We initialize the diagonal elements of the dp array as true because a single character is always a palindrome. Then, we check for palindromic substrings of length 2 and update the dp array accordingly.

Next, we iterate over all possible lengths greater than 2 and fill the dp array based on the recurrence relation: dp[i][j] = (str[i] == str[j]) && dp[i + 1][j - 1].

Finally, we return the longest palindromic substring by using the substr function with the starting index and length obtained from the dp array.

Also Read: C Program to Find the Inverse of 2×2 Matrix

The main function demonstrates the usage of the findLongestPalindrome function by providing a sample string “babad” as input.

Program to Find Longest Palindromic Substring in Java

Implementation in Java

In Java, we can leverage the built-in functionalities of the String class to find the longest palindromic substring. Here is an implementation in Java:

public class LongestPalindromicSubstring {
    public static String findLongestPalindrome(String str) {
        int n = str.length();
        boolean[][] dp = new boolean[n][n];

        int maxLength = 1;
        int start = 0;

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            if (i < n - 1 && str.charAt(i) == str.charAt(i + 1)) {
                dp[i][i + 1] = true;
                maxLength = 2;
                start = i;
            }
        }

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    maxLength = len;
                    start = i;
                }
            }
        }

        return str.substring(start, start + maxLength);
    }

    public static void main(String[] args) {
        String str = "babad";
        String longestPalindrome = findLongestPalindrome(str);
        System.out.println("Longest palindromic substring: " + longestPalindrome);
    }
}

Explanation

The Java program follows a similar approach to the C++ program using dynamic programming. We use a 2D boolean array dp to store the palindrome information for substrings.

After initializing the dp array, we iterate through the input string and update the array based on the conditions mentioned earlier.

Also Read: Length of String C++: Tips and Tricks for Effective Programming

Finally, we return the longest palindromic substring using the substring method.

The main function demonstrates the usage of the findLongestPalindrome method by providing the sample string “babad” as input.

Program to Find Longest Palindromic Substring in Python

Implementation in Python

Python provides an elegant and concise syntax that simplifies the implementation of algorithms. Here is an implementation of finding the longest palindromic substring in Python:

def find_longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]

    max_length = 1
    start = 0

    for i in range(n):
        dp[i][i] = True
        if i < n - 1 and s[i] == s[i + 1]:
            dp[i][i + 1] = True
            max_length = 2
            start = i

    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                max_length = length
                start = i

    return s[start:start + max_length]


str = "babad"
longest_palindrome = find_longest_palindrome(str)
print("Longest palindromic substring:", longest_palindrome)

Explanation

The Python implementation is similar to the previous implementations, but with a more concise syntax. We use a 2D boolean list dp to store the palindrome information for substrings.

After initializing the dp list, we iterate through the input string and update the list based on the conditions mentioned earlier. Finally, we return the longest palindromic substring using string slicing.

The main part of the code demonstrates the usage of the find_longest_palindrome function by providing the sample string “babad” as input.

Frequently Asked Questions (FAQs)

Conclusion

In this article, we explored different programming languages, including C, C++, Java, and Python, to find the longest palindromic substring.

We discussed the implementations using both the brute-force approach and more optimized algorithms like dynamic programming.

By understanding these techniques, you can efficiently solve the problem of finding the longest palindromic substring and improve your programming skills.

Remember to choose the appropriate algorithm based on the requirements of your project and consider the time complexity of the solution.