LeetCode 5 Solution

Problem Statement (LeetCode 5 - Longest Palindromic Substring)

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

Example Input & Output

Example 1

Input: s = "babad"
Output: "bab"  (or "aba" is also a valid answer)

Example 2

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

Example 3

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

Example 4

Input: s = "ac"
Output: "a" (or "c")

---

Optimal Approach: Expand Around Center

Intuition

A palindrome expands symmetrically from its center.

• Every palindrome has a center (either a single character or between two characters).
• We expand outward to find the longest possible palindrome.

Steps to Solve

1. Iterate through each character in s as a center.
2. Expand outward for:
   • Odd-length palindromes (single character center).
   • Even-length palindromes (two-character center).
3. Update the longest palindrome found.

Time & Space Complexity

• Time Complexity: O(n²) (Each character expansion takes O(n), iterating over n characters).
• Space Complexity: O(1) (Only a few extra variables).

---

LeetCode-Compatible C++ Code

#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        int start = 0, maxLength = 1;
        
        for (int i = 0; i < s.size(); i++) {
            int len1 = expandAroundCenter(s, i, i);     // Odd-length palindrome
            int len2 = expandAroundCenter(s, i, i + 1); // Even-length palindrome
            int len = max(len1, len2);
            
            if (len > maxLength) {
                start = i - (len - 1) / 2;
                maxLength = len;
            }
        }
        
        return s.substr(start, maxLength);
    }

private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // Length of palindrome
    }
};

---

Step-by-Step Explanation

Expand Around Center

1. For each character s[i]:
   • Expand odd-length palindrome around s[i].
   • Expand even-length palindrome around s[i] and s[i+1].
2. Track the longest palindrome found.
3. Return the substring from start index with length maxLength.

---

Dry Run Example

Input: "babad"

Expansions:

Center	Expands To	Palindrome Found
b	bab	bab (length 3)
a	aba	aba (length 3)
b	bab	bab (length 3)
a	aba	aba (length 3)
d	d	d (length 1)

Output: "bab" (or "aba" is also valid)

---

Alternative Approaches & Why Not?

1️⃣ Brute Force (Check All Substrings)

• Generate all substrings and check if they are palindromes.
• Time Complexity: O(n³)
• Space Complexity: O(1)
• ❌ Too slow for large inputs!

2️⃣ Dynamic Programming (DP)

• Use dp[i][j] = true if s[i:j] is a palindrome.
• Time Complexity: O(n²)
• Space Complexity: O(n²)
• ✅ Faster than brute force but requires O(n²) extra space.

3️⃣ Manacher's Algorithm (O(n) Solution)

• Preprocess string with # to handle even-length cases.
• Use a radius array to store palindrome lengths.
• Time Complexity: O(n)
• Space Complexity: O(n)
• ✅ Fastest approach but complex to implement.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Expand Around Center (Best)	O(n²)	O(1)	Simple & efficient
Brute Force	O(n³)	O(1)	Too slow
Dynamic Programming (DP)	O(n²)	O(n²)	Uses extra memory
Manacher’s Algorithm	O(n)	O(n)	Fastest but complex

---

Conclusion

• The Expand Around Center approach is the best balance of simplicity and efficiency.
• Manacher’s Algorithm is the fastest (O(n)), but complex to implement.
• Brute force and DP methods are slower and use more space.

---

Recommended Problems for Practice

1. Palindromic Substrings
2. Longest Palindromic Subsequence
3. Valid Palindrome II

Master Palindrome Expansions and optimize your Dynamic Programming skills to solve similar problems efficiently! 🚀