Wezual Code

Longest Palindromic Substring: Explained with Java and Python Code

author
Digambar Patil

The Longest Palindromic Substring problem is a classic challenge in the realm of string manipulation. In this blog, we will delve into the intricacies of finding the longest palindromic substring in a given string. Through a step-by-step approach and illustrative examples, you will gain a comprehensive understanding of the problem and learn how to solve it efficiently.

 

Understanding the Problem:

A palindrome is a string that reads the same forward and backward. The Longest Palindromic Substring problem requires finding the longest substring within a given string that is also a palindrome. Our goal is to determine the length of this substring and return the substring itself.

 

Approach:

To solve the Longest Palindromic Substring problem, we can employ a dynamic programming approach or use the expanding around center technique. Here, we will explore the dynamic programming approach.

  1. Create a boolean table, dp, of size [n][n] (where n is the length of the input string) to store whether substrings are palindromes.
  2. Initialize the table such that dp[i][i] is true (single characters are palindromes) and dp[i][i+1] is true if s[i] equals s[i+1] (two adjacent characters are the same).
  3. Iterate through the input string, starting with substrings of length 3 and gradually increasing the length.
  4. For each substring, check if the current characters are the same and if the inner substring is also a palindrome. If both conditions are true, mark dp[i][j] as true.
  5. Keep track of the longest palindromic substring encountered and its length.
  6. Finally, return the longest palindromic substring.

 

Example: Let's illustrate the dynamic programming approach with an example:

Input: "babad"

We initialize the dp table as follows:

 

b a b a d

 

b T T

a T

b T

a T

d T

Starting with substrings of length 3, we check if the outer characters are the same and if the inner substring is also a palindrome. In this case, we find "bab" and mark dp[0][2] as true. We continue this process until we have checked all substrings.

The longest palindromic substring in this case is "bab" with a length of 3.

 

Java Implementation: 

Let's start with the Java implementation of finding the Longest Palindromic Substring:

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int maxLength = 1;

        // Single character substrings are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // Check for palindromic substrings of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }

        // Check for palindromic substrings of length > 2
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLength = len;
                }
            }
        }

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

    public static void main(String[] args) {
        LongestPalindromicSubstring lps = new LongestPalindromicSubstring();
        String input = "babad";
        String longestPalindrome = lps.longestPalindrome(input);
        System.out.println("Longest Palindromic Substring: " + longestPalindrome);
    }
}

 

Python Implementation:

Now, let's explore the Python implementation of finding the Longest Palindromic Substring:

class LongestPalindromicSubstring:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        start = 0
        maxLength = 1

        # Single character substrings are palindromes
        for i in range(n):
            dp[i][i] = True

        # Check for palindromic substrings of length 2
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                maxLength = 2

        # Check for palindromic substrings of length > 2
        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
                    start = i
                    maxLength = length

        return s[start:start + maxLength]


lps = LongestPalindromicSubstring()
input_str = "babad"
longest_palindrome = lps.longestPalindrome(input_str)
print("Longest Palindromic Substring:", longest_palindrome)

 

Conclusion:

The Longest Palindromic Substring problem is a fascinating challenge that tests our string manipulation skills. By understanding the problem, exploring the dynamic programming approach, and examining the provided example, you now have the tools to solve this problem efficiently. Feel free to experiment with different input strings and further optimize the code to meet your specific requirements.

String
Leetcode
Dynamic Programming