Practice/Uber/Leetcode 5. Longest Palindromic Substring

Leetcode 5. Longest Palindromic Substring

CodingMust

Problem

Write a function that takes a string and returns the longest contiguous substring that reads the same forward and backward (a palindrome). If there are multiple palindromic substrings of the same maximum length, you may return any one of them.

A palindrome is a sequence of characters that remains unchanged when reversed. For example, "racecar" and "noon" are palindromes, while "hello" is not.

Requirements

1. Return the actual palindromic substring, not just its length
2. If multiple palindromes tie for the longest length, any valid answer is acceptable
3. A single character counts as a palindrome
4. The solution should handle both odd-length palindromes (like "aba") and even-length palindromes (like "abba")

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of only lowercase and/or uppercase English letters
• Target time complexity: O(n²) or better
• Target space complexity: O(1) auxiliary space (not counting the output string)

Examples

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. Both are palindromes of length 3.

Example 2:

Input: s = "cbbd" Output: "bb" Explanation: The longest palindrome is "bb" with length 2.

Example 3:

Input: s = "a" Output: "a" Explanation: A single character is inherently a palindrome.

Example 4:

Input: s = "racecar" Output: "racecar" Explanation: The entire string is a palindrome.