TIC
The Interns Company

Longest Palindromic Substring

MediumAcceptance: 35.5%
StringDynamic Programming

Problem Statement

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

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Input Format:

  • A string s

Output Format:

  • The longest palindromic substring

Examples:

Example 1:

Input:

s = "babad"

Output:

"bab"

Explanation:

"aba" is also a valid answer.

Example 2:

Input:

s = "cbbd"

Output:

"bb"

Explanation:

The longest palindromic substring is "bb".

Example 3:

Input:

s = "a"

Output:

"a"

Explanation:

A single character is always a palindrome.

Solutions

Expand Around Center

Time: O(n²)
Space: O(1)

Check each position as a potential center and expand outwards.

Dynamic Programming

Time: O(n²)
Space: O(n²)

Use a 2D array to track whether each substring is a palindrome.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. Input: s = "babad"
  2. Initialize start = 0, maxLength = 1
  3. Iterate through each position as potential palindrome center:
  4. i = 0, character 'b':
  5. Odd center: expand(0,0) → palindrome 'b', length 1
  6. Even center: expand(0,1) → not a palindrome ('ba')
  7. i = 1, character 'a':
  8. Odd center: expand(1,1) → palindrome 'a', length 1
  9. Even center: expand(1,2) → not a palindrome ('ab')
  10. i = 2, character 'b':
  11. Odd center: expand(2,2) → palindrome 'b', length 1
  12. Even center: expand(2,3) → palindrome 'ba', expands to 'bab', length 3
  13. Update start = 0, maxLength = 3
  14. i = 3, character 'a':
  15. Odd center: expand(3,3) → palindrome 'a', length 1
  16. Even center: expand(3,4) → not a palindrome ('ad')
  17. i = 4, character 'd':
  18. Odd center: expand(4,4) → palindrome 'd', length 1
  19. Even center: expand(4,5) → out of bounds
  20. Result: s.substring(0, 3) = "bab"

Hints

Hint 1
Consider every position as a potential center of palindrome.
Hint 2
A palindrome can be centered at a character (odd length) or between characters (even length).
Hint 3
Expand around each potential center and find the longest palindrome.

Video Tutorial

Longest Palindromic Substring - Expand Around Center Technique

YouTube•Learn the Longest Palindromic Substring solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the expansion process around each center position and track the longest palindromic substring found.

Key visualization elements:

  • current center
  • expanding boundaries
  • current longest palindrome

Similar Questions

Palindromic Substrings

Medium

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Asked By

AmazonMicrosoftGoogleFacebookAdobeAppleBloombergLinkedIn

Implementation Notes

The 'Expand Around Center' approach is generally preferred due to its simplicity and O(1) space complexity, despite both approaches having the same time complexity. For very long strings, the DP approach might be faster in practice due to better cache locality.