Table of contents

Longest Palindromic Substring in a string

Given a string s, find the longest palindromic substring in s. If there are multiple substrings of the same length, return the one that appears first.

Input-Output Examples

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer, but "bab" appears first.

Example 2:

Input: s = "cbbd"
Output: "bb"

Approach:
Technique: Dynamic Programming

  1. Initialization: Create a 2D array dp where dp[i][j] represents whether the substring s[i..j] is a palindrome.
  2. Filling the DP Table:
    • Single characters are palindromes by default (dp[i][i] = true).
    • Check for palindromes of length 2 and greater by expanding around each possible center.
    • If s[i] == s[j] and dp[i+1][j-1] is true, then dp[i][j] = true.
  3. Track the Longest Palindrome: Keep track of the start and end indices of the longest palindrome found.
  4. Return: The substring defined by the start and end indices.

C++ Program to find the Longest Palindromic Substring

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Function to find the longest palindromic substring
string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLength = 1;
    
    // All substrings of length 1 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[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    
    // Check for palindromes of length greater than 2
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }
    return s.substr(start, maxLength);
}

int main() {
    string s = "babad";
    string result = longestPalindrome(s);
    cout << "Longest Palindromic Substring: " << result << endl;
    return 0;
}

Java Program to find the Longest Palindromic Substring

java
public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        String s = "babad";
        String result = longestPalindrome(s);
        System.out.println("Longest Palindromic Substring: " + result);
    }

    // Function to find the longest palindromic substring
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1;
        
        // All substrings of length 1 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;
                start = i;
                maxLength = 2;
            }
        }
        
        // Check for palindromes of length greater than 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);
    }
}

Python Program to find the longest palindromic substring

python
def longestPalindrome(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    dp = [[False] * n for _ in range(n)]
    start, maxLength = 0, 1
    
    # All substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Check for palindromes 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 palindromes of length greater than 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]

if __name__ == "__main__":
    s = "babad"
    result = longestPalindrome(s)
    print(f"Longest Palindromic Substring: {result}")

These codes include the main function and the necessary function for finding the longest palindromic substring using dynamic programming. The longestPalindrome function calculates the longest palindromic substring by filling a DP table and tracking the start and end indices of the longest palindrome found.

DSA

Related Articles