5. Longest Palindromic Substring - Leetcode

Longest Palindromic Substring

Problem Statement

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 consists of only digits and English letters.

Approaches

Expand Around Center Approach

Explanation:

  • 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.
  • This approach is efficient with O(n^2) time complexity and O(1) space complexity.
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
    }
}

Dynamic Programming Approach

Explanation:

  • 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.
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)
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);
    }
}

Brute Force Approach

Explanation:

  • Check all substrings of s to determine if they are palindromic.
  • This is inefficient for large input sizes.
  • Time Complexity: O(n^3)
  • Space Complexity: O(1)
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

Expand Around Center:

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

Dynamic Programming:

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

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"

Featured Posts

3. Longest Substring Without Repeating Characters - Leetcode

Longest Substring Without Repeating Characters Difficulty: Medium Problem Statement: Given a string s , find the length of the longest ...

Popular Posts