Longest Palindromic Substring | LeetCode Problem Solution | Interview bit Solution

Introduction:
The Longest Palindromic Substring problem is a classic computer science challenge that involves finding the longest substring within a given string that reads the same forwards and backwards. In this blog, we’ll discuss the problem statement, approach, and provide a Java solution to solve this problem. Additionally, we’ll provide solutions for both LeetCode and InterviewBit platforms.

Problem Statement:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Approach:
To solve this problem, we can use a dynamic programming approach. We’ll create a 2D boolean array dp, where dp[i][j] will be true if the substring from index i to index j is a palindrome. We’ll initialize all single characters as palindromes and then fill the table for longer substrings based on the palindromic property of smaller substrings.

Solution:
Here’s the Java program that implements the dynamic programming approach to find the longest palindromic substring:

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 1;  // Minimum palindrome length is 1
        int start = 0;      // Starting index of the longest palindrome substring

        // All individual characters are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

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

        // Check for palindromes of length >= 3
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;  // Ending index of current substring

                // Check if current substring is palindrome
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > maxLength) {
                        maxLength = len;
                        start = i;
                    }
                }
            }
        }

        // Extract and return the longest palindromic substring
        return s.substring(start, start + maxLength);
    }

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

Conclusion:
In this blog post, we discussed the Longest Palindromic Substring problem and provided a detailed Java solution using a dynamic programming approach. This solution effectively finds the longest palindromic substring within a given input string. By understanding and implementing this approach, you can tackle similar algorithmic challenges and improve your problem-solving skills.