[Dynamic Programming] Longest Palindromic Substring (Advanced DP) - Hard

The Longest Palindromic Substring problem is a well-known challenge in dynamic programming. It aims to find the longest part of a string that reads the same from both ends. To solve this problem, we can look for centers of palindromes and expand them. We can also use a dynamic programming table to keep track of results. This helps us to solve overlapping parts more easily.

In this article, we will look at the Longest Palindromic Substring problem closely. First, we will understand the problem. Then, we will see how to solve it using dynamic programming in Java, Python, and C++. We will also discuss the expanding around center technique. We will visualize how to build the dynamic programming table. We will look at ways to save space and compare different methods. We will answer some common questions about this topic too.

  • Dynamic Programming Longest Palindromic Substring Advanced DP Hard
  • Understanding the Longest Palindromic Substring Problem
  • Dynamic Programming Approach to Longest Palindromic Substring in Java
  • Dynamic Programming Approach to Longest Palindromic Substring in Python
  • Dynamic Programming Approach to Longest Palindromic Substring in C++
  • Expanding Around Center Technique for Longest Palindromic Substring
  • Dynamic Programming Table Construction Visualization
  • Optimizing Space Complexity in Longest Palindromic Substring
  • Comparative Analysis of Approaches for Longest Palindromic Substring
  • Frequently Asked Questions

If you want to learn more about dynamic programming, you can check these articles: Dynamic Programming Fibonacci Number and Dynamic Programming Minimum Cost Climbing Stairs.

Understanding the Longest Palindromic Substring Problem

The Longest Palindromic Substring problem is a well-known problem in computer science. It is important in the area of dynamic programming. Our goal is to find the longest part of a string that reads the same backward and forward. This part is called a palindrome.

Problem Definition

We have a string s. Our task is to find the longest palindromic substring inside s. For example: - Input: "babad" - Output: "bab" (or "aba" because both are correct)

Characteristics of Palindromes

  • A palindrome can be even or odd in length.
  • Here are some examples:
    • Even length: "abba"
    • Odd length: "racecar"

Constraints

  • The length of the string can be from 1 to 1000.
  • Our solution needs to work well with big strings because of time complexity.

Example Cases

  1. Single Character: Any single character is a palindrome.
    • Input: "a"
    • Output: "a"
  2. No Palindrome: If there are no repeated characters.
    • Input: "abc"
    • Output: "a" (or "b" or "c")
  3. Complex Case:
    • Input: "cbbd"
    • Output: "bb"

We can solve this problem in many ways. Some methods are brute-force, dynamic programming, and expanding around the center. We will look at these methods in the next sections.

If you want to learn more about dynamic programming methods, you can read Dynamic Programming: Fibonacci Number and other similar problems.

Dynamic Programming Approach to Longest Palindromic Substring in Java

We solve the Longest Palindromic Substring problem using Dynamic Programming in Java. We use a 2D array dp. The value dp[i][j] shows if the substring from index i to index j is a palindrome.

Steps to implement:

  1. Initialization:
    • Every single character is a palindrome. So we set dp[i][i] = true for all i.
    • Next, we check for two character palindromes: dp[i][i+1] = (s[i] == s[i+1]).
  2. Dynamic Programming Table Construction:
    • For substrings longer than 2, we use this formula:
      • dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
    • We also track the start index and maximum length of the longest palindrome we find.
  3. Algorithm Complexity:
    • Time Complexity is O(n^2) because of the nested loops.
    • Space Complexity is O(n^2) for the DP table.

Java Implementation:

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, maxLength = 1;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

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

        // Check for two character palindromes
        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 longer than 2 characters
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLength = length;
                }
            }
        }

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

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

Explanation of the Code:

We start the longestPalindrome method. It initializes the DP table and fills it based on the rules we said before. The main method shows how to call this function with a test string.

For more about dynamic programming, we can look at other articles like Dynamic Programming - Longest Common Subsequence and Dynamic Programming - Palindromic Substrings Count.

Dynamic Programming Approach to Longest Palindromic Substring in Python

We can solve the Longest Palindromic Substring problem using dynamic programming in Python. We create a 2D table to keep track of whether substrings are palindromic. The algorithm builds the solution step by step by checking substrings of different lengths.

Algorithm Steps

  1. Initialization: We create a 2D list dp with size n x n. Here, n is the length of the input string. We set all entries to False. Single character substrings are palindromes. So we set dp[i][i] = True for all i.

  2. Check for Two Character Palindromes: For substrings of length 2, we set dp[i][i+1] = True if s[i] == s[i+1].

  3. Check for Longer Substrings: For substrings longer than 2, we use this rule:

    • dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] == True.

  4. Track the Longest Palindrome: We keep track of the start index and the maximum length of the longest palindromic substring we find.

Python Implementation

def longest_palindromic_substring(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""

    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

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

    # Two character substrings
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2

    # Substrings of length 3 and greater
    for length in range(3, n + 1):  # length of substring
        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
                max_length = length

    return s[start:start + max_length]

# Example Usage
input_string = "babad"
print(longest_palindromic_substring(input_string))  # Output: "bab" or "aba"

Complexity Analysis

  • Time Complexity: O(n^2) where n is the length of the input string. We are filling an n x n table.
  • Space Complexity: O(n^2) for the dp table.

This method finds the longest palindromic substring well. We can use similar ways in other languages like Java and C++. If we want to learn more about different methods, we can check other resources like Dynamic Programming on Longest Common Subsequence or Minimum Insertions to Form a Palindrome.

Dynamic Programming Approach to Longest Palindromic Substring in C++

The Longest Palindromic Substring problem is a well-known dynamic programming problem. It asks us to find the longest substring in a given string that reads the same forwards and backwards. In C++, we can use a dynamic programming table to solve this problem effectively.

Dynamic Programming Table Setup

  1. Initialization: We create a 2D boolean array dp with size n x n. Here, n is the length of the input string s. Each entry dp[i][j] shows if the substring s[i..j] is a palindrome.

  2. Base Cases:

    • Each single character is a palindrome: dp[i][i] = true.
    • For two-character palindromes: dp[i][i + 1] = (s[i] == s[i + 1]).

  3. Filling the DP Table: For substrings longer than two characters, we use this relation:

    • dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1].

  4. Tracking the Longest Palindrome: We keep track of the start index and the maximum length of the longest palindromic substring we find.

C++ Implementation

Here is the C++ code for the dynamic programming approach:

#include <iostream>
#include <vector>
#include <string>

std::string longestPalindrome(std::string s) {
    int n = s.size();
    if (n < 1) return "";

    std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
    int start = 0, maxLength = 1;

    // Base cases
    for (int i = 0; i < n; i++) {
        dp[i][i] = true; // single letter palindromes
    }

    for (int i = 0; i < n - 1; i++) {
        dp[i][i + 1] = (s[i] == s[i + 1]); // two letter palindromes
        if (dp[i][i + 1]) {
            start = i;
            maxLength = 2;
        }
    }

    // Fill the DP table
    for (int length = 3; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
            if (dp[i][j] && length > maxLength) {
                start = i;
                maxLength = length;
            }
        }
    }

    return s.substr(start, maxLength);
}

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

Explanation of the Code

  • Dynamic Array Initialization: We make a 2D vector dp and set it to false.
  • Base Case Handling: We check for single and two-character palindromes first.
  • Dynamic Programming Table Filling: We build the solution for longer substrings using results we computed before.
  • Result Extraction: We use the starting index and maximum length to get the substring from the original string.

This approach has a time complexity of O(n^2) and space complexity of O(n^2). It works well for strings of moderate length. If we want to reduce space complexity, we can use different methods. You can read more in articles like Optimizing Space Complexity in Longest Palindromic Substring.

Expanding Around Center Technique for Longest Palindromic Substring

The Expanding Around Center technique is good for finding the longest palindromic substring in a string. This method works on the idea that a palindrome is the same forwards and backwards. So, we can look at each character and each pair of characters in the string. We then expand outwards to check for palindromes.

Algorithm Steps

  1. Initialize Variables:
    • We keep a variable to track the longest palindromic substring we find.
  2. Iterate through Each Character:
    • For each character in the string, we expand around it as the center.
    • We also look at the space between pairs of characters for even-length palindromes.
  3. Expand Outwards:
    • We keep expanding as long as the characters on both sides are the same.
  4. Update the Longest Palindrome:
    • If we find a longer palindrome while expanding, we update our longest substring variable.

Time Complexity

  • The time complexity of this method is O(n^2). Here n is the length of the string. Each expansion can take linear time in the worst case.

Space Complexity

  • The space complexity is O(1). We only use a few variables to track the indices.

Implementation

Here is how we can implement the Expanding Around Center technique in Python, Java, and C++.

Python Implementation:

def longest_palindromic_substring(s: str) -> str:
    def expand_around_center(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    longest = ""
    for i in range(len(s)):
        odd_palindrome = expand_around_center(i, i)
        even_palindrome = expand_around_center(i, i + 1)
        longest = max(longest, odd_palindrome, even_palindrome, key=len)
    
    return longest

Java Implementation:

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            String oddPalindrome = expandAroundCenter(s, i, i);
            String evenPalindrome = expandAroundCenter(s, i, i + 1);
            longest = longest.length() > oddPalindrome.length() ? longest : oddPalindrome;
            longest = longest.length() > evenPalindrome.length() ? longest : evenPalindrome;
        }
        return longest;
    }

    private String expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}

C++ Implementation:

class Solution {
public:
    string longestPalindrome(string s) {
        string longest = "";
        for (int i = 0; i < s.size(); i++) {
            string oddPalindrome = expandAroundCenter(s, i, i);
            string evenPalindrome = expandAroundCenter(s, i, i + 1);
            longest = longest.size() > oddPalindrome.size() ? longest : oddPalindrome;
            longest = longest.size() > evenPalindrome.size() ? longest : evenPalindrome;
        }
        return longest;
    }

    string expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};

Summary

The Expanding Around Center technique gives us a simple way to find the longest palindromic substring. It has a clear O(n^2) time complexity and O(1) space complexity. This method is useful because it checks palindromes using symmetry. For more on dynamic programming techniques, we can look at articles like Dynamic Programming - Longest Palindromic Subsequence.

Dynamic Programming Table Construction Visualization

We need to understand the dynamic programming (DP) table. It is very important for solving the Longest Palindromic Substring problem. The DP table helps us keep track of results we have already calculated. This makes our calculations faster.

Table Structure

For the Longest Palindromic Substring problem, we use a 2D boolean DP table called dp[i][j]. Here: - i and j are the positions in the string. - dp[i][j] is true if the substring from i to j is a palindrome.

Initialization

  1. Single Character Substrings: Each single character is a palindrome.

    for (int i = 0; i < n; i++) {
    dp[i][i] = true;
}

  2. Two Character Substrings: We check if two characters next to each other are the same.

    for (int i = 0; i < n - 1; i++) {
    dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}

Filling the DP Table

We fill the DP table for substrings that are longer than two characters. For any substring s[i..j] to be a palindrome: - s[i] must be the same as s[j] - The substring s[i+1..j-1] must also be a palindrome.

The code to fill out the table looks like this:

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

Example Table Visualization

For the string “babad”, the DP table will look like this after we process it:

b a b a d
b T F T F F
a F T F T F
b T F T F F
a F T F T F
d F F F F T

The table shows that: - “bab” (from index 0 to 2) is a palindrome. - “aba” (from index 1 to 3) is also a palindrome.

Conclusion

Using the DP table helps us check for palindromic substrings quickly. We can find the longest one by keeping track of previous results. This way, we save time compared to a simple method. This approach is very important in dynamic programming problems, especially for string tasks.

If you want to learn more about dynamic programming, you can read articles on Dynamic Programming - Fibonacci Number or Dynamic Programming - Longest Palindromic Subsequence.

Optimizing Space Complexity in Longest Palindromic Substring

When we solve the Longest Palindromic Substring problem with dynamic programming, we usually need O(n^2) space. This is to store the DP table, where n is the length of the input string. But we can make it better. We can reduce the space to O(1) by using the special properties of palindromes and a method called expanding around the center.

Space Optimization Techniques

  1. Reducing the DP Table Size: Instead of using a big 2D table, we can just use two boolean arrays. They will help us keep track of the current and previous states of the palindrome check.

  2. Expanding Around Center: This method lets us check for palindromes by expanding around each character. We do this for both odd and even-length palindromes. This way, we do not need a full DP table.

Implementation in Java

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);   // Odd length
            int len2 = expandAroundCenter(s, i, i + 1); // Even length
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Implementation in Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 1:
            return ""
        start, end = 0, 0

        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)    # Odd length
            len2 = self.expandAroundCenter(s, i, i + 1) # Even length
            length = max(len1, len2)
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2
        return s[start:end + 1]

    def expandAroundCenter(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

Implementation in C++

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() < 1) return "";
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);   // Odd length
            int len2 = expandAroundCenter(s, i, i + 1); // Even length
            int length = max(len1, len2);
            if (length > end - start) {
                start = i - (length - 1) / 2;
                end = i + length / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

By using these methods, we make the space use go from O(n^2) to O(1). We still find the longest palindromic substring fast. This is very helpful for big strings where memory is a big deal. If you want to learn more about dynamic programming, check out Dynamic Programming: Longest Palindromic Subsequence.

Comparative Analysis of Approaches for Longest Palindromic Substring

When we solve the Longest Palindromic Substring problem, we can use different methods. Each method has its own good points and some downsides. In this section, we will look at three common methods: Dynamic Programming, Expanding Around Center, and Manacher’s Algorithm.

1. Dynamic Programming (DP)

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Approach: - We make a 2D table. In this table, dp[i][j] is true if the substring from index i to j is a palindrome. - We start by marking single characters as palindromes (dp[i][i] = true) and check two-character substrings. - Then we fill the table for substrings of length 3 and more using this rule: - If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1].

Example:

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) return s;
    boolean[][] dp = new boolean[n][n];
    String longest = "";
    
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > longest.length()) {
                    longest = s.substring(i, j + 1);
                }
            }
        }
    }
    return longest;
}

2. Expanding Around Center

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach: - We look at each character and the gap between each pair of characters as centers for palindromes. - We then expand outwards to check if these are palindromes.

Example:

def longestPalindrome(s: str) -> str:
    if len(s) < 1:
        return ""
    
    start, end = 0, 0
    
    for i in range(len(s)):
        len1 = expandAroundCenter(s, i, i)  # Odd length
        len2 = expandAroundCenter(s, i, i + 1)  # Even length
        max_len = max(len1, len2)
        
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
            
    return s[start:end + 1]

def expandAroundCenter(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

3. Manacher’s Algorithm

Time Complexity: O(n)
Space Complexity: O(n)

Approach: - We change the original string to avoid problems with even and odd lengths. - We use an array to store the radius of palindromes at each position. - We keep track of the rightmost boundary of the palindrome we found so far to make the expansion faster.

Example:

string preprocess(string s) {
    string t = "^#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    t += '$';
    return t;
}

string longestPalindrome(string s) {
    string T = preprocess(s);
    int n = T.length();
    vector<int> P(n, 0);
    int center = 0, right = 0;
    
    for (int i = 1; i < n - 1; i++) {
        if (i < right) {
            P[i] = min(right - i, P[2 * center - i]);
        }
        while (T[i + P[i] + 1] == T[i - P[i] - 1]) {
            P[i]++;
        }
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }
    
    int maxLen = 0, maxCenter = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            maxCenter = i;
        }
    }
    
    return s.substr((maxCenter - 1 - maxLen) / 2, maxLen);
}

Summary of Comparisons

  • Dynamic Programming is easy to understand but uses O(n^2) space. This makes it not so good for big strings.
  • Expanding Around Center uses less space and is still O(n^2) in time. It usually works better in practice.
  • Manacher’s Algorithm is the fastest with O(n) time. It is best for long strings but is harder to understand.

Depending on what we need for the problem, we can choose the best method to find the longest palindromic substring. For more information on dynamic programming, we can check articles like Dynamic Programming - Longest Palindromic Subsequence or Dynamic Programming - Count of Palindromic Substrings.

Frequently Asked Questions

What is the longest palindromic substring problem?

The longest palindromic substring problem is about finding the longest part of a string that reads the same from both sides. This is a common example in dynamic programming. We can solve it with different methods, like the expanding around center method. Knowing this problem helps us learn more about dynamic programming, especially in string handling.

How can I implement the longest palindromic substring in Java?

To do the longest palindromic substring in Java, we can use dynamic programming. First, we make a 2D array to keep results of palindrome checks. Then, we go through the string and update this array based on what we checked before. This way, we can check palindromic substrings more efficiently. For more details, look at our section on Dynamic Programming Approach to Longest Palindromic Substring in Java.

What is the time complexity of finding the longest palindromic substring?

When we use dynamic programming to find the longest palindromic substring, the time complexity is O(n^2). Here, n is the length of the string we use. This happens because we check all possible substrings. For each substring, we may need to check if it is a palindrome. Other methods, like the expanding around center method, can also reach O(n^2) time complexity but they can be faster in practice.

How can I optimize space complexity for the longest palindromic substring?

To make space usage better for the longest palindromic substring problem, we can change the 2D table to a 1D array. We only need the previous state to compute the current state. This change makes space usage go from O(n^2) to O(n) but keeps the O(n^2) time complexity. For more information, check our section on Optimizing Space Complexity in Longest Palindromic Substring.

Are there alternative methods to solve the longest palindromic substring problem?

Yes, there are other ways too. Besides the dynamic programming way, we can use the expanding around center technique. This method is easier and has a time complexity of O(n^2) but only needs O(1) space. We treat each character and pairs of characters as possible centers for palindromes and expand outwards. For examples, look at our section on the Expanding Around Center Technique for Longest Palindromic Substring.