🌱 Keegan's Digital Garden

5. Longest Palindromic Substring

3 min read

📝 Problem Details

input string s return the longest palindromic substring (a substring that is also a palindrome) palindrome: reads the same forwards as it does backward

💭What Were My Initial Thoughts?

Can be solved with more than just one approach:

1. DP where we identify the subproblem as:
	- a substring s[i : j] is a palindrome if:
		- the first and last characters match (s[i] == s[j]) and
		- the substring between them s[i+1 : j−1] is also a palindrome

2. Expand Around Center Approach:
	- treat each character (or pair of adjacent chars) as a potential center of a pelindrome and expand outward to find the longest palindrome

🤔What Did I Struggle With?

- the non-dp approach was more intuitive to come up with 
- had trouble with defining the subproblem and the state for the DP approach

💡 Explanation of Solution

DP approach:

1. subproblem identification:
	- a substring s[i : j] is a palindrome if:
		- the first and last characters match (s[i] == s[j]) and
		- the substring between them s[i+1 : j−1] is also a palindrome

2. top-down or bottom-up:
	- can do either
	- bottom-up: start by making all single characters palindromes
	- for every substring length >= 2, check if it is a palindrome based on its smaller inner substring

3. dp state:
	- 2D DP table where dp[i][j] is true if the substring s[i : j] inclusive is a palindrome
	- base case: all substrings of length 1 are palindromes
	- substrings of length 2: they are palindromes if s[i] == s[i+1]
	- for longer substrings:
		- s[i] == s[j] and dp[i+1][j-1] is true

4. transition formula:
	- dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])

5. space optimization:
- non-dp approach --> see Expand Around Center Approach

⌛ Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n^2)
can be optimized to O(1) if not using DP

💻 Implementation of Solution

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
 
        if(n == 0) return "";
 
        // dp table
        vector<vector<bool>> dp(n, vector<bool>(n, false));
 
        int start = 0, maxLength = 1; // store the lognest palindrome start index
 
        // base case: single character substring
        for(int i=0; i < n; i++) {
            dp[i][i] = true;
        }
 
        // base case: two character substrings
        for(int i=0; i < n-1; i++) {
            if(s[i] == s[i+1]) {
                dp[i][i+1] = true;
                start = i;
                maxLength = 2;
            }
        }
 
        // fill the dp table for substrings of length 3 or more
        for (int len = 3; len <= n; len++) { // len is substring length
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1; // End index of substring
 
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLength = len;
                }
            }
        }
 
        return s.substr(start, maxLength);
    }
};

Graph View