05.Longest Palindromic Substring

📘 LeetCode 5: Longest Palindromic Substring

📌 Problem Overview

• Problem Number: 5
• Problem Name: Longest Palindromic Substring
• Difficulty: Medium
• Category: 1D Dynamic Programming
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the 1D Dynamic Programming algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/5.Longest-Palindromic-Substring/:

using System;
 
Console.WriteLine($"babad -> {LongestPalindrome("babad")}");
Console.WriteLine($"cbbd -> {LongestPalindrome("cbbd")}");
 
string LongestPalindrome(string s)
{
    if (string.IsNullOrEmpty(s)) return "";
    int start = 0, maxLength = 1;
 
    for (int i = 0; i < s.Length; i++)
    {
        // Odd length palindrome
        ExpandAroundCenter(s, i, i, ref start, ref maxLength);
        // Even length palindrome
        ExpandAroundCenter(s, i, i + 1, ref start, ref maxLength);
    }
 
    return s.Substring(start, maxLength);
}
 
void ExpandAroundCenter(string s, int left, int right, ref int start, ref int maxLength)
{
    while (left >= 0 && right < s.Length && s[left] == s[right])
    {
        int currentLength = right - left + 1;
        if (currentLength > maxLength)
        {
            start = left;
            maxLength = currentLength;
        }
        left--;
        right++;
    }
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.