5. Longest Palindromic Substring

Description

Longest Palindromic Substring
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.

Approach

• We use a method of expansion where for a given left and right index we expand left and right and check if the characters are equal
• Two kind of expansion odd where start index is same for both and for even i and i + 1
• Remember - after loop completion we would have reached one one index extra towards either side and also substring includes start and excludes end
• Time: O(n^2) Space: O(1)
• There is one more O(n) way while using Manacher's Algorithm which is designed for this

class Solution {
    public String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = expand(s,i,i);
            String even = expand(s,i,i+1);
            if (longest.length() < odd.length())
                longest = odd;
            if (longest.length() < even.length())
                longest = even;    
        }
        return longest;
    }
 
    public String expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}

Approach 1: Brute Force ($O(N^3)$ Time, $O(1)$ Space)

Intuition

Check every possible substring ($O(N^2)$ pairs of start and end indices) and verify whether it forms a palindrome ($O(N)$ time check). Track and return the longest valid palindromic substring found.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n <= 1) return s;
 
        String maxStr = "";
 
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j) && (j - i + 1) > maxStr.length()) {
                    maxStr = s.substring(i, j + 1);
                }
            }
        }
 
        return maxStr;
    }
 
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
 

Complexity

• Time Complexity: $O(N^3)$ — Generating $O(N^2)$ substrings, with each requiring $O(N)$ character comparisons.
• Space Complexity: $O(1)$ auxiliary space (excluding the output string).

---

Approach 2: Expand Around Center (Optimal — $O(N^2)$ Time, $O(1)$ Space)

Intuition

A palindrome mirrors around its center. Instead of checking every substring from the outside in, treat each index (and pair of adjacent indices) as a center and expand outward as long as the characters match:

1. Odd Length Palindromes: Center at a single character (i, i).
2. Even Length Palindromes: Center between two adjacent characters (i, i + 1).

Maintain the start and end boundaries of the longest palindrome found during expansion.

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 (e.g. "aba")
            int len2 = expandAroundCenter(s, i, i + 1); // Even length (e.g. "abba")
            int len = Math.max(len1, len2);
 
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
 
        return s.substring(start, end + 1);
    }
 
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1; // Return length of expanded palindrome
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — There are $2N-1$ potential centers, and expanding from each center takes $O(N)$ time in the worst case.
• Space Complexity: $O(1)$ auxiliary space.

This block updates the boundaries (start and end) of the longest palindrome found so far.

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

1. The Condition

end - start + 1 represents the length of the current best palindrome. If len is greater, a new longer palindrome has been found.

2. The Index Formulas

Given the center index i and total palindrome length len, the formulas calculate how far left and right the palindrome extends:

• start = i - (len - 1) / 2: Moves left from center i to the start boundary.
• end = i + len / 2: Moves right from center i to the end boundary.

Why the Math Works for Both Odd and Even Lengths

Because of integer division rounding down in Java:

• Odd Length (e.g., len = 3, center i = 2 for "aba"):
  • start = $2-(3-1)/2=2-1=1$
  • end = $2+3/2=2+1=3$
• Even Length (e.g., len = 4, center left i = 2 for "abba"):
  • start = $2-(4-1)/2=2-1=1$
  • end = $2+4/2=2+2=4$

• In normal circumstances, the length of a window from index left to right is right - left + 1.The reason it changes to - 1 here is because of when the while loop stops. The pointers start and end move past the valid boundaries before the loop breaks.