Longest Palindromic Substring

Introduction
Today we're solving one of LeetCode's classic string problems - finding the longest palindromic substring. This is problem #5, and it's an excellent way to understand dynamic programming and center expansion techniques in string algorithms.

The Problem
Given a string s, return the longest substring that reads the same forwards and backwards (a palindrome).

Example:
'''
Input: "babad"
Output: "bab" or "aba"
Explanation: Both "bab" and "aba" are valid palindromic substrings.
'''

The Optimal Solution
'''typescript
function longestPalindrome(s: string): string {
let start = 0;
let end = 0;

for (let i = 0; i < s.length; i++) {
    const [left1, right1] = expandAroundCenter(s, i, i);
    const [left2, right2] = expandAroundCenter(s, i, i + 1);

    if (right1 - left1 > end - start) {
        start = left1;
        end = right1;
    }
    if (right2 - left2 > end - start) {
        start = left2;
        end = right2;
    }
}

return s.substring(start, end + 1);

}

function expandAroundCenter(s: string, left: number, right: number): [number, number] {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return [left + 1, right - 1];
}
'''

This solution is:
✅ Efficient - O(n²) time complexity (optimal for this problem)
✅ Space-optimized - O(1) additional space
✅ Clean - Uses simple center expansion logic
✅ Handles both odd and even length palindromes

How It Works
Center Expansion Technique: Checks each character (and between characters) as potential palindrome centers

Dual Expansion: Expands for both odd-length (single center) and even-length (dual center) palindromes

Bounds Tracking: Maintains the start/end indices of the longest palindrome found

Length Comparison: Continuously updates when longer palindromes are found

Alternative Approaches
Dynamic Programming Approach:
'''typescript
function longestPalindrome(s: string): string {
const n = s.length;
const dp: boolean[][] = Array(n).fill(false).map(() => Array(n).fill(false));
let result = '';

for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
        dp[i][j] = s[i] === s[j] && (j - i < 3 || dp[i + 1][j - 1]);
        if (dp[i][j] && j - i + 1 > result.length) {
            result = s.substring(i, j + 1);
        }
    }
}
return result;

}
'''
Pros:

• Systematic approach using DP table
• Easier to understand the recurrence relation

Cons:

• O(n²) space complexity
• More complex implementation
• Slower due to table initialization

Brute Force Approach:
'''typescript
function longestPalindrome(s: string): string {
let longest = '';
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substr = s.substring(i, j + 1);
if (isPalindrome(substr) && substr.length > longest.length) {
longest = substr;
}
}
}
return longest;
}

function isPalindrome(s: string): boolean {
return s === s.split('').reverse().join('');
}
'''
Pros:

• Simple to understand
• No advanced concepts needed

Cons:

• O(n³) time complexity
• Extremely inefficient for longer strings

Edge Cases to Consider

• Empty string
• Single character string ("a")
• All characters same ("aaaaa")
• No palindromes longer than 1 character ("abcde")
• Even-length palindromes ("abba")
• Mixed case with special characters

Performance Considerations
The optimal solution:

• Processes each character as a potential center
• Expands outward in O(n) time per center
• Total O(n²) time complexity (optimal for this problem)
• Uses constant space (just stores indices)

Common Mistakes to Avoid

• Forgetting to check both odd and even length palindromes
• Incorrect bounds when expanding from center
• Not updating the longest palindrome properly
• Off-by-one errors in substring extraction
• Not handling edge cases like empty strings

Real-world Applications
This algorithm has practical uses in:

• DNA sequence analysis (palindromic sequences)
• Cryptography (pattern matching)
• Data compression (finding repeated patterns)
• Text processing (finding mirrored structures)
• Plagiarism detection (finding similar structures)

Conclusion
The center expansion approach provides the best combination of:
🔥 Optimal O(n²) time complexity
🔥 Minimal O(1) space usage
🔥 Clean implementation
🔥 Robust handling of all edge cases

Understanding this center expansion technique will help with many other string manipulation problems. It's a fundamental pattern that demonstrates how we can often find efficient solutions by looking for natural symmetries in problems!