/longest-palindromic-substring-c

C solution to a LeetCode #5 (Longest Palindromic Substring) problem, fully documented and analyzed with an emphasis on optimal runtime and memory efficiency.

Primary LanguageC

Longest Palindromic Substring

LeetCode Problem #5

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

Examples

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

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

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

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

Constraints

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

Hints (from the original LeetCode problem)

  1. How can we reuse a previously computed palindrome to compute a larger palindrome?
  2. If "aba" is a palindrome, is "xabax" a palindrome? Similarly, is "xabay" a palindrome?
  3. Complexity-based hint:
    • A brute-force check of every start and end index has O(n²) pairs and O(n) per check.
    • Can we reduce the palindromic check to O(1) by reusing previous computations?

LeetCode Final Analysis (Screenshots)

Runtime Memory

💭 My Reaction

Honestly, I’m happy with how this solution turned out.
The time complexity being O(n²) makes sense for this type of approach,
and the space complexity staying at O(n) feels efficient enough.

Right now, I’m also learning Manacher’s algorithm, and I plan to use it in the future.
I didn’t use it this time because I didn’t know it yet,
and I don’t like copying code for things I don’t understand.
When I learn it properly, I’ll implement it myself and compare the results.