Longest Palindromic Substring medium

Problem Statement

Given a string s, find the longest palindromic substring in s.

Example 1

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2

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

Steps

The solution uses a dynamic programming approach. We'll create a table dp where dp[i][j] is true if the substring s[i...j] is a palindrome, and false otherwise. We'll build this table iteratively, starting with substrings of length 1, then length 2, and so on.

1. Initialization: All single characters are palindromes (length 1 substrings). Also, all two-character substrings that are the same are palindromes (length 2 substrings).

2. Iteration: For substrings of length 3 and greater, s[i...j] is a palindrome if and only if s[i] == s[j] and s[i+1...j-1] is also a palindrome (which we'll already know from previous calculations).

3. Tracking the Longest Palindrome: While building the dp table, we'll keep track of the start and end indices of the longest palindrome found so far.

Explanation

The dynamic programming approach efficiently avoids redundant calculations. Once we determine if a substring is a palindrome, we don't need to re-check it later. The table dp stores the results of these subproblems, allowing us to build up the solution efficiently. The time complexity is O(n^2) because we iterate through all possible substrings. The space complexity is also O(n^2) due to the dp table.

Code

#include <string>
#include <algorithm>

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int n = s.length();
        if (n < 2) return s; // Handle base cases

        bool dp[n][n]; // dp[i][j] is true if s[i...j] is a palindrome
        int start = 0;
        int maxLength = 1;


        // Initialize for substrings of length 1
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }

        //Check for substrings 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;
            } else {
                dp[i][i+1] = false;
            }
        }

        //Check for substrings of length 3 or greater
        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;
                    if (len > maxLength) {
                        start = i;
                        maxLength = len;
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return s.substr(start, maxLength);
    }
};

Complexity

• Time Complexity: O(n^2), where n is the length of the string. This is due to the nested loops in the dynamic programming approach.
• Space Complexity: O(n^2), where n is the length of the string. This is due to the dp table used for dynamic programming. The space could be optimized to O(n) if we only store the previous row of the DP table. However, the given solution prioritizes readability and clarity.