Introduction

A palindrome is a string that reads the same from left to right and right to left.

A palindromic substring is a continuous part of a string that forms a palindrome.

The goal is to find the longest palindromic substring in the given string.

For example, in "babad", the longest palindromic substrings are "bab" and "aba".

Problem Statement

Given a string, find the longest substring that is a palindrome.

Example

Input:
"babad"

Output:
"bab"

Note:
"aba" is also a valid answer.

Constraints

  • 1 ≤ n ≤ 1000
  • The string contains lowercase or uppercase English letters.
  • The substring must be continuous.

Approach 1: Brute Force

Explanation

The brute-force approach checks every possible substring.

For each substring:

  1. Check whether it is a palindrome.
  2. If it is a palindrome and its length is greater than the current answer, store it.

There can be O(n²) substrings, and checking each substring can take O(n) time.

Steps

  1. Generate every possible substring.
  2. Check whether the substring is a palindrome.
  3. Compare its length with the longest palindrome found.
  4. Store the longest one.
  5. Return the result.

Dry Run

Input:"babad"

Possible palindromes:
"b"     → palindrome
"a"     → palindrome
"b"     → palindrome
"a"     → palindrome
"d"     → palindrome
"bab"   → palindrome
"aba"   → palindrome

Longest length = 3

Result:
"bab"

Brute Force Code

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(1) excluding the output string.

Approach 2: Optimized Solution Using Expand Around Center

Explanation

Every palindrome has a center.

There are two types of palindromes:

  • Odd-length palindrome → one center character
  • Even-length palindrome → two center characters

For every possible center, expand outward while the characters are equal.

For example:

 "babad"      a
      ↓
b a b a d

Expand around "a":
b a b

Result:
"bab"

We check both odd and even centers to find the longest palindrome.

Steps

  1. Consider every character as a possible center.
  2. Expand left and right for an odd-length palindrome.
  3. Consider every gap between two characters as a center.
  4. Expand left and right for an even-length palindrome.
  5. Keep track of the longest palindrome.
  6. Return the longest substring.

Dry Run

Input:"babad"

Center at index 1:
b [a] b

Expand:
a matches a
b matches b

Palindrome:
"bab"

Center at index 2:
[a] b [a]

Expand:
b matches b

Palindrome:
"aba"

Longest length = 3

Result:
"bab"

Optimized Code

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(1) excluding the output string.

Edge Cases

  • Single character → the character itself is the answer.
  • All characters different → any single character is the longest palindrome.
  • Entire string is a palindrome → return the entire string.
  • Even-length palindrome → such as "abba".
  • Odd-length palindrome → such as "racecar".
  • Multiple longest palindromes → any one valid longest palindrome can be returned.

Why This Problem is Important

This problem teaches an important technique called Expand Around Center.

It is useful for understanding:

  • Palindromes
  • Two-pointer techniques
  • String traversal
  • Center-based expansion
  • Optimization from brute force

Real-World Applications

Palindrome detection and substring analysis are useful in:

  • Text processing
  • Pattern analysis
  • DNA sequence analysis
  • Natural language processing
  • Search and text algorithms

Common Mistakes

  1. Checking only odd-length palindromes.
  2. Forgetting even-length palindromes.
  3. Confusing a substring with a subsequence.
  4. Returning a palindrome that is not the longest.
  5. Using incorrect left and right boundaries during expansion.

Interview Tips

  • Start with the brute-force approach.
  • Explain why checking every substring leads to O(n³) time.
  • Introduce the idea that every palindrome has a center.
  • Check both odd and even length palindromes.
  • Remember that "bab" and "aba" are both valid answers for "babad".

Related Questions

  • Check Whether a String Is a Palindrome
  • Count Palindromic Substrings
  • Longest Common Substring
  • Valid Palindrome II
  • Palindromic Substrings

Final Takeaway

The Longest Palindromic Substring problem can be solved efficiently using the Expand Around Center technique.

The optimized approach checks every possible center and expands outward, reducing the time complexity from O(n³) to O(n²).