Blind 75 - problem 18 : longest palindromic substring

 

Longest Palindromic Substring - LeetCode Solution & Explanation

Problem Statement

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

A palindrome is a sequence of characters that reads the same forward and backward.

Constraints

• 1 <= s.length <= 1000
• s consists only of lowercase and uppercase English letters.

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"

---

Optimal Approach: Expand Around Center

Key Idea:

A palindrome expands symmetrically around its center.
For each character (or pair of characters), we expand outward while maintaining the palindrome property.

Steps:

1. Check for both Odd and Even length palindromes.
   • Odd-length: Expand around single character.
   • Even-length: Expand around two adjacent characters.
2. Keep track of the longest palindrome found.

Time Complexity: O(n²)

Space Complexity: O(1)

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    string expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
    
    string longestPalindrome(string s) {
        if (s.length() <= 1) return s;

        string longest = "";
        for (int i = 0; i < s.length(); i++) {
            // Odd-length palindrome
            string oddPal = expandAroundCenter(s, i, i);
            if (oddPal.length() > longest.length()) {
                longest = oddPal;
            }

            // Even-length palindrome
            string evenPal = expandAroundCenter(s, i, i + 1);
            if (evenPal.length() > longest.length()) {
                longest = evenPal;
            }
        }
        return longest;
    }
};

---

Step-by-Step Explanation

1. Edge Case: If the string length is 1, return it directly.
2. Expand Around Center: Iterate through the string:
   • Try expanding around a single character (odd-length palindromes).
   • Try expanding around two adjacent characters (even-length palindromes).
3. Update the Longest Palindrome:
   • If the found palindrome is longer than the current longest, update it.
4. Return the Longest Palindrome.

---

Dry Run (Execution Steps)

Let's take s = "babad":

Step 1: Checking each character

Index	Odd-length Expansion	Even-length Expansion	Longest Found
i = 0	"b"	""	"b"
i = 1	"bab"	"ba"	"bab"
i = 2	"aba"	"ad"	"bab"
i = 3	"a"	"d"	"bab"
i = 4	"d"	""	"bab"

Final Output: "bab"

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Check all substrings)	O(n³)	O(1)	Too slow for n = 1000
Dynamic Programming (DP Table)	O(n²)	O(n²)	Uses extra memory
Expand Around Center (Best)	O(n²)	O(1)	Efficient & no extra memory

---

Best Solution & Why?

The Expand Around Center approach is the best because:
✅ O(n²) Time Complexity – Handles n=1000 efficiently.
✅ O(1) Space Complexity – No extra DP table needed.
✅ Simple & Elegant Code – Easy to implement with a helper function.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force (All Substrings)	O(n³)	O(1)
Dynamic Programming (DP Table)	O(n²)	O(n²)
Expand Around Center (Best)	O(n²)	O(1)

---

Conclusion

• Best Approach: Expand Around Center (O(n²) time, O(1) space).
• Why? Avoids recursion, extra memory, and handles large inputs efficiently.
• Similar Problems to Practice:
  1. Palindrome Partitioning LeetCode #131
  2. Longest Palindromic Subsequence LeetCode #516
  3. Valid Palindrome LeetCode #125