# Longest Palindromic Substring

The "Longest Palindromic Substring" problem is a classic challenge in computer science, particularly in string processing and dynamic programming. It involves identifying the longest substring within a given string that reads the same forwards and backwards. Let's dissect this problem using fundamental principles of algorithms and string processing.

### Problem Statement:

1. Input: A string.
2. Goal: Find the longest substring which is a palindrome.

### Fundamental Concepts:

• String: A sequence of characters.
• Substring: A contiguous sequence of characters within a string.
• Palindrome: A string that reads the same forwards and backwards. For example, "racecar" is a palindrome.

### Solution Approaches:

1. Brute Force Method:

• Idea: Check every possible substring to see if it's a palindrome.
• Time Complexity: O(n³), where n is the length of the string. This is because there are O(n²) substrings, and checking each for being a palindrome takes O(n) time.
• Space Complexity: O(1), as no extra space is required apart from the input string.
• Practicality: Not efficient for large strings due to high time complexity.
2. Expand Around Center:

• Idea: Consider each character (and each pair of adjacent characters for even-length palindromes) as the middle of a potential palindrome and expand outwards.
• Implementation: For each character (or character pair), expand outwards while the substring is a palindrome.
• Time Complexity: O(n²), since for each of the n characters, expansion in both directions takes O(n) time in the worst case.
• Space Complexity: O(1), only constant extra space is needed.
3. Dynamic Programming:

• Idea: Use a table to store the results of subproblems; a substring is a palindrome if its outer characters match and its inner substring is also a palindrome.
• Implementation: Create a boolean table dp[i][j] that is true if the substring from index i to j is a palindrome.
• Time Complexity: O(n²), since we fill a table of size n².
• Space Complexity: O(n²), for the table.

### Example Implementation (Expand Around Center in Python):

Here's an example using the "Expand Around Center" method:

def longest_palindromic_substring(s):
"""
Finds the longest palindromic substring in s.

Args:
s (str): The input string.

Returns:
str: The longest palindromic substring.
"""
def expand_around_center(left, right):
"""Expands around the center and returns the longest palindrome."""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

longest = ""
for i in range(len(s)):
# Odd length palindrome
tmp = expand_around_center(i, i)
if len(tmp) > len(longest):
longest = tmp

# Even length palindrome
tmp = expand_around_center(i, i + 1)
if len(tmp) > len(longest):
longest = tmp

return longest


This implementation:

• Iterates through each character in the string, treating each as the center of a potential palindrome.
• Expands around the center for both odd and even length palindromes.
• Uses a helper function expand_around_center to find the longest palindrome centered at the given indices.
• Updates the longest palindrome found so far.

This approach efficiently finds the longest palindromic substring with significantly less time complexity compared to brute force, making it suitable for a wide range of input string sizes.