Longest Palindromic Substring 🎯

Welcome to our deep dive into the fascinating world of Longest Palindromic Substring! In this lesson, we'll explore how to find the longest palindromic substring in a given string, a problem that is often encountered in competitive programming and real-world applications. Let's get started!

What is a Palindromic Substring? 📝

A palindromic substring is a sequence of characters within a string that reads the same forwards and backwards. For example, "racecar" is a palindrome, as is "level" within the string "deified level".

Finding the Longest Palindromic Substring 💡

To find the longest palindromic substring in a given string, we will use a simple algorithm that builds upon the idea of comparing characters on both sides of the center of the substring. Let's dive into the details.

Manacher's Algorithm 📝

The Manacher's algorithm is a dynamic programming approach that solves the problem of finding the longest palindromic substring in O(n) time complexity, where n is the length of the input string. Here's a breakdown of the algorithm:

Initialize an array P of length n+1, where P[i] represents the palindromic length centered at the ith index. If the string is empty, P[0] = 0.
Expand all possible palindromes from the center outwards. For each index i, check the left and right neighbors i-1 and i+1 to find the maximum palindromic length centered at i-1-k and i+1+k for some k. Update P[i] accordingly.
Find the maximum palindromic length by finding the maximum value in the P array.

Code Example 💻

Let's see a Python implementation of the Manacher's algorithm:

python

def longest_palindrome(s):
    n = len(s)
    P = [0] * (n + 1)
    center, right = 0, 0

    for i in range(1, n + 1):
        P[i] = 1
        left, right = i - 1, i + 1

        while left >= 0 and right < n and s[left] == s[right]:
            P[i] += 1
            left -= 1
            right += 1

    max_length = max(P)
    max_center = P.index(max_length)

    return s[max_center - (max_length - 1) // 2 : max_center + (max_length - 1) // 2 + 1]

Quiz

That's it for our detailed lesson on the Longest Palindromic Substring! With this knowledge, you're ready to tackle problems involving palindromic substrings in competitive programming and various real-world applications.

Remember to practice regularly, and soon you'll be finding the longest palindromic substrings like a pro! 🚀

Quiz