Leetcode 5. LongestPalindromic Substring

 5. LongestPalindromic Substring

Medium, Dynamic Programming

Given a string s, return 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"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

To solve the Longest Palindromic Substring problem, we aim to find the largest contiguous substring of the input s that is a palindrome.

---

Approaches:

1. Expand Around Center:

   • Every palindrome is centered at either a single character or a pair of characters.
   • Expand around each center to find the longest palindrome, checking both odd-length and even-length cases.

2. Dynamic Programming:

   • Use a 2D table dp where dp[i][j] is true if the substring s[i...j] is a palindrome.
   • Transition:
     • dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] is true (or if the length is less than 3).
   • Track the longest palindrome during the process.

3. Brute Force:

   • Check all substrings of s to determine if they are palindromic. This is inefficient for large input sizes.

---

Implementation (Expand Around Center Approach):

This approach is efficient and works in $O(n^2)$ time with $O(1)$ space.

public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s) || s.Length < 1) return "";

        int start = 0, end = 0;

        for (int i = 0; i < s.Length; i++) {
            int len1 = ExpandFromCenter(s, i, i);     // Odd-length palindromes
            int len2 = ExpandFromCenter(s, i, i + 1); // Even-length palindromes
            int len = Math.Max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.Substring(start, end - start + 1);
    }

    private int ExpandFromCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // Length of the palindrome
    }
}

---

Implementation (Dynamic Programming Approach):

This approach uses $O(n^2)$ time and $O(n^2)$ space.

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == null || s.Length == 0) return "";

        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int start = 0, maxLength = 0;

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i, j] = (len == 1 || len == 2) || dp[i + 1, j - 1];
                    if (dp[i, j] && len > maxLength) {
                        start = i;
                        maxLength = len;
                    }
                }
            }
        }

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

---

Implementation (Brute Force Approach):

This is straightforward but inefficient, as it checks all substrings.

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == null || s.Length == 0) return "";

        string longest = "";

        for (int i = 0; i < s.Length; i++) {
            for (int j = i; j < s.Length; j++) {
                if (IsPalindrome(s, i, j) && (j - i + 1 > longest.Length)) {
                    longest = s.Substring(i, j - i + 1);
                }
            }
        }

        return longest;
    }

    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
}

---

Complexity Analysis:

1. Expand Around Center:

   • Time Complexity: $O(n^2)$ — Each center expansion takes $O(n)$, and there are $O(n)$ centers.
   • Space Complexity: $O(1)$.

2. Dynamic Programming:

   • Time Complexity: $O(n^2)$ — Filling the DP table.
   • Space Complexity: $O(n^2)$ — Storing the DP table.

3. Brute Force:

   • Time Complexity: $O(n^3)$ — Checking all substrings and validating each palindrome.
   • Space Complexity: $O(1)$.

---

Example Outputs:

Example 1:

• Input: s = "babad"
• Output: "bab" or "aba"

Example 2:

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

Example 3:

• Input: s = ""
• Output: ""

Example 4:

• Input: s = "a"
• Output: "a"