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() {
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 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 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]

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.

1. What is a palindrome?

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

2. Why is finding the longest palindromic substring important?

Finding the longest palindromic substring is important in various applications such as DNA analysis, data compression, and pattern recognition.

3. Are there any efficient algorithms for finding the longest palindromic substring?

Yes, there are efficient algorithms like Manacher’s algorithm that can find the longest palindromic substring in linear time complexity.

4. Can the longest palindromic substring be found using brute-force approach?

Yes, the brute-force approach can find the longest palindromic substring, but it has higher time complexity compared to optimized algorithms.

5. Are the provided implementations applicable to other programming languages?

Yes, the logic behind the implementations can be applied to other programming languages with minor modifications.

6. What are some real-world applications of finding the longest palindromic substring?

Some applications include DNA sequence analysis, text processing, and anomaly detection in data streams.

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.