Approach

Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

A palindrome is a string that reads the same forward and backward.

Examples

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

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

Example 3:

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

Constraints

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

Approach

Key Insight

Palindrome properties:

A palindrome reads the same forward and backward
To expand a palindrome, characters on both ends must match
Single characters and two identical characters are base cases

Solution 1: Dynamic Programming (2D Table)

Build a 2D DP table where dp[i][j] indicates if s[i:j+1] is a palindrome.

Algorithm:

Create 2D boolean array dp[n][n]
Base cases:
- All single characters are palindromes: dp[i][i] = true
- Two character palindromes: dp[i][i+1] = (s[i] == s[i+1])
For substrings of length 3+:
- dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
Track longest palindrome found

Complexity:

Time: O(n²) - fill n×n table
Space: O(n²) - 2D DP table

Solution 2: Expand Around Center

For each possible center, expand outward while characters match.

Algorithm:

For each index as center:
- Expand for odd-length palindromes (single center)
- Expand for even-length palindromes (two centers)
Track longest palindrome found

Key points:

Two cases: odd length (center at i) and even length (center between i and i+1)
Expand while left and right characters match

Complexity:

Time: O(n²) - n centers × O(n) expansion
Space: O(1) - only variables

Solution 3: Manacher's Algorithm

Linear time algorithm using clever preprocessing and symmetry properties.

Algorithm:

Transform string with sentinels: "babad" → "^#b#a#b#a#d#$"
Use array to store palindrome radii
Leverage symmetry to avoid redundant checks
Find center with maximum radius

Complexity:

Time: O(n) - each character visited once
Space: O(n) - radius array

Complexity Analysis

| Approach | Time | Space | |----------|------|-------| | 2D DP | O(n²) | O(n²) | | Expand Around Center | O(n²) | O(1) | | Manacher's | O(n) | O(n) |

Pattern Recognition

This problem demonstrates:

Dynamic Programming with 2D table
Two Pointers technique (expand around center)
String manipulation
Optimization trade-offs (space vs time)
Similar patterns: Palindrome Partitioning, Palindromic Substrings

Solution

java

1class Solution {
2    // Solution 1: Dynamic Programming (2D Table)
3    public String longestPalindrome(String s) {
4        if (s == null || s.length() == 0) return "";
5
6        int n = s.length();
7        boolean[][] dp = new boolean[n][n];
8        int start = 0;
9        int maxLen = 1;
10
11        // Base case: single characters
12        for (int i = 0; i < n; i++) {
13            dp[i][i] = true;
14        }
15
16        // Base case: two characters
17        for (int i = 0; i < n - 1; i++) {
18            if (s.charAt(i) == s.charAt(i + 1)) {
19                dp[i][i + 1] = true;
20                start = i;
21                maxLen = 2;
22            }
23        }
24
25        // Fill table for substrings of length 3+
26        for (int len = 3; len <= n; len++) {
27            for (int i = 0; i <= n - len; i++) {
28                int j = i + len - 1;
29
30                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
31                    dp[i][j] = true;
32                    start = i;
33                    maxLen = len;
34                }
35            }
36        }
37
38        return s.substring(start, start + maxLen);
39    }
40
41    // Solution 2: Expand Around Center
42    public String longestPalindromeExpand(String s) {
43        if (s == null || s.length() == 0) return "";
44
45        int start = 0;
46        int maxLen = 0;
47
48        for (int i = 0; i < s.length(); i++) {
49            // Odd length palindrome (single center)
50            int len1 = expandAroundCenter(s, i, i);
51            // Even length palindrome (two centers)
52            int len2 = expandAroundCenter(s, i, i + 1);
53
54            int currentLen = Math.max(len1, len2);
55            if (currentLen > maxLen) {
56                maxLen = currentLen;
57                start = i - (currentLen - 1) / 2;
58            }
59        }
60
61        return s.substring(start, start + maxLen);
62    }
63
64    private int expandAroundCenter(String s, int left, int right) {
65        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
66            left--;
67            right++;
68        }
69        return right - left - 1;
70    }
71
72    // Solution 3: Manacher's Algorithm
73    public String longestPalindromeManacher(String s) {
74        if (s == null || s.length() == 0) return "";
75
76        // Transform: "babad" -> "^#b#a#b#a#d#$"
77        StringBuilder sb = new StringBuilder("^");
78        for (char c : s.toCharArray()) {
79            sb.append('#').append(c);
80        }
81        sb.append("#$");
82        String t = sb.toString();
83
84        int n = t.length();
85        int[] p = new int[n]; // Array of palindrome radii
86        int center = 0;
87        int right = 0;
88
89        for (int i = 1; i < n - 1; i++) {
90            // Mirror of i with respect to center
91            int mirror = 2 * center - i;
92
93            // Use previously computed values
94            if (i < right) {
95                p[i] = Math.min(right - i, p[mirror]);
96            }
97
98            // Expand around i
99            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
100                p[i]++;
101            }
102
103            // Update center and right boundary
104            if (i + p[i] > right) {
105                center = i;
106                right = i + p[i];
107            }
108        }
109
110        // Find maximum palindrome
111        int maxLen = 0;
112        int centerIndex = 0;
113        for (int i = 1; i < n - 1; i++) {
114            if (p[i] > maxLen) {
115                maxLen = p[i];
116                centerIndex = i;
117            }
118        }
119
120        // Extract substring from original string
121        int start = (centerIndex - maxLen) / 2;
122        return s.substring(start, start + maxLen);
123    }
124
125    // Solution 4: Optimized Expand (Track Best)
126    public String longestPalindromeOptimized(String s) {
127        if (s == null || s.length() == 0) return "";
128
129        String result = "";
130
131        for (int i = 0; i < s.length(); i++) {
132            // Skip if remaining string can't beat current best
133            if (result.length() >= 2 * (s.length() - i)) {
134                break;
135            }
136
137            // Check odd and even length palindromes
138            String odd = expand(s, i, i);
139            String even = expand(s, i, i + 1);
140
141            // Update result if longer found
142            if (odd.length() > result.length()) {
143                result = odd;
144            }
145            if (even.length() > result.length()) {
146                result = even;
147            }
148        }
149
150        return result;
151    }
152
153    private String expand(String s, int left, int right) {
154        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
155            left--;
156            right++;
157        }
158        return s.substring(left + 1, right);
159    }
160}
161