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 to Solve

The problem can be solved using a dynamic programming approach or an optimized approach using expanding around the center. We'll detail the expanding around the center method as it's generally more efficient.

1. Initialization: We'll iterate through each character in the string. Each character is a palindrome of length 1.

2. Expanding Around Center: For each character, we consider it as a potential center of a palindrome. We then expand outwards, checking if the characters to the left and right are equal. We maintain a variable to track the longest palindrome found so far. Crucially, we must consider two cases for each center: one where the center is a single character, and one where the center is two identical characters.

3. Updating Longest Palindrome: As we expand, if we find a longer palindrome, we update the start and end indices of the longest palindrome found.

Explanation

The expanding around the center approach is efficient because it avoids redundant checks. Instead of checking all possible substrings, it focuses only on potential palindrome centers and expands outwards. This significantly reduces the time complexity compared to a brute-force or naive dynamic programming approach.

Code (Java)

class Solution {
    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 palindromes
            int len2 = expandAroundCenter(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 + 1);
    }

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

Complexity Analysis

• Time Complexity: O(n^2), where n is the length of the string. In the worst case (e.g., a string of all the same character), we might need to expand outwards for almost all possible centers. However, this is still significantly faster than the O(n^3) complexity of a naive approach.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input string size. We are not storing any large auxiliary data structures.