5. Longest Palindromic Substring

TL;DR

Thoughts and Talk

I must admit, I too once viewed palindromes as mere intellectual curiosities, intriguing puzzles for the mathematically inclined. However, delving deeper into their applications has unveiled a world of practical significance that extends far beyond the realm of recreational brain teasers.

In the field of genetics, palindromic sequences emerge as invaluable tools for unraveling the intricate tapestry of DNA structures. These unique patterns aid researchers in deciphering the very building blocks of life, unlocking insights that could pave the way for groundbreaking discoveries and advancements in healthcare and biotechnology.

Yet, the practical utility of palindromes does not end there. Cryptographers, tasked with the vital responsibility of safeguarding digital information, have found ingenious ways to harness the power of palindromes. By meticulously crafting robust passwords and encryption keys employing intricate string manipulation techniques, they fortify our digital defenses against ever-evolving cyber threats.

While these real-world applications certainly lend credence to the significance of palindromes, I cannot help but ponder the minds behind the coding challenges that introduced us to these intriguing concepts. Somewhere, a mathematician or computer scientist, driven by an insatiable curiosity and a deep appreciation for the elegance of patterns, may have crafted these problems as a means to challenge and inspire future generations of problem solvers. May be, we never know! Instead what we know is that there are atleast four ways to solve this problem, and we are sure that we know three of them and we are writing about only one of those three ways that we used to solve this problem

Just in case if you don’t already know -

Palindromes are strings that read the same from both directions. For example, "racecar" and "noon" are palindromes, while "hello" and "world" are not.

The challenge in this problem lies in finding the longest substring within a given string that is a palindrome.

Problem Statement

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

Example 1:


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

Example 2:


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

Example 3:


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

Hints

Brute Force Approach: A straightforward way to solve this problem is to generate all possible substrings of the given string and check if each substring is a palindrome. However, this approach is inefficient for large strings due to its time complexity of O(n^3), where n is the length of the input string.

Dynamic Programming Approach: Another way to solve this problem is by using dynamic programming. This approach involves building a table that stores the information about whether a substring is a palindrome or not. However, this approach can be challenging to implement and may require additional space proportional to the length of the input string.

Expand Around Center Approach: The most efficient solution to this problem is based on the idea of expanding a palindrome from its center. This approach takes advantage of the fact that palindromes can be expanded from their center outwards.

Approaches Explored

Approach 1: Brute Force

The brute force approach involves generating all possible substrings of the given string and checking if each substring is a palindrome. We can then keep track of the longest palindromic substring found so far.

Pros:

Simple and easy to understand
Straightforward implementation

Cons:

Time complexity of O(n^3), making it inefficient for large strings
Not an optimal solution for interview settings

Approach 2: Dynamic Programming

The dynamic programming approach involves building a 2D table to store the information about whether a substring is a palindrome or not. We can then use this table to find the longest palindromic substring.

Pros:

Time complexity of O(n^2), which is better than the brute force approach
Space complexity of O(n^2), as we need to store the table

Cons:

Relatively complex implementation
Additional space required to store the table

Finalized Approach: Expand Around Center

When I was trying to move away from brute force, my penchance for trees and graphs gave me an idea, what if we could pull up each array index as a root node of the tree? We need to loop only once, and we would iterate only once and check for palindromes!

The most efficient solution to this problem, in this blog, is the "Expand Around Center" approach. This approach takes advantage of the fact that palindromes can be expanded from their center outwards. Here's how it works:

We iterate through the string and treat each character as a potential center of a palindrome.

For each potential center, we expand outwards (to the left and right) as long as the characters on both sides are the same.

We keep track of the longest palindromic substring found so far.

This approach has a time complexity of O(n^2), which is better than the brute force approach, and a space complexity of O(1), as we don't need to store any additional data structures.

Executable Code

TheTechCruise.com Pyodide Terminal

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start, end = 0, 0

        def expand_around_center(left: int, right: int) -> None:
            nonlocal start, end
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            left += 1
            right -= 1

            if (right - left) > (end - start):
                start, end = left, right

        for i in range(len(s)):
            expand_around_center(i, i)
            if i + 1 < len(s) and s[i] == s[i + 1]:
                expand_around_center(i, i + 1)

        return s[start:end + 1]
if __name__ == "__main__":
    solution = Solution()
    test_cases = [
        ("babad", "bab"),
        ("cbbd", "bb"),
        ("a", "a"),
        ("cbbbbd", "bbbb"),
        ("acbbbbca", "bbbbb"),
        ("acbbbba", "bbbbb"),
        ("caba", "aba")
    ]

    for s, expected in test_cases:
        result = solution.longestPalindrome(s)
        print(f"Input: {s}, Output: {result}, Expected: {expected}, Result: {result == expected}")

Example, Explanation, and Code Walkthrough

Let's go through the code with different examples to understand how it works.

Example 1: "babad"


Input: s = "babad"
Output: "bab" or "aba"

In this example, we have two palindromic substrings of length 3: "bab" and "aba". Let's follow the code step-by-step:

We initialize start and end to keep track of the longest palindromic substring found so far.

We define a helper function expand_around_center(left, right) that expands a potential palindrome outwards from its center.

We iterate through the string, treating each character as a potential center of a palindrome.

For the character 'b' at index 0, we call expand_around_center(0, 0) to check for odd-length palindromes. This expands to the left and right until the characters are different, updating start and end if a longer palindrome is found.

For the character 'a' at index 1, we call expand_around_center(1, 1) to check for odd-length palindromes. This expands to the left and right until the characters are different, updating start and end if a longer palindrome is found.

For the character 'b' at index 2, we call expand_around_center(2, 2) to check for odd-length palindromes. This expands to the left and right until the characters are different, updating start and end if a longer palindrome is found.

For the character 'a' at index 3, we call expand_around_center(3, 3) to check for odd-length palindromes. This expands to the left and right until the characters are different, updating start and end if a longer palindrome is found.

For the character 'd' at index 4, we call expand_around_center(4, 4) to check for odd-length palindromes. This does not expand further, as the characters on both sides are different.

Additionally, we check for even-length palindromes by calling expand_around_center(0, 1), expand_around_center(1, 2), expand_around_center(2, 3), and expand_around_center(3, 4). The call expand_around_center(1, 2) expands to the substring "aba", updating start and end to represent the longest palindromic substring found so far.

After iterating through the entire string, start and end point to the indices of the longest palindromic substring, "aba".

The function returns s[start:end + 1], which is "aba".

Example 2: "abc"


Input: s = "abc"
Output: "a" or "b" or "c"

In this example, there are no palindromic substrings of length greater than 1. The code will iterate through the string, calling expand_around_center for each character. Since none of the expansions can form a palindrome longer than a single character, the function will return the first character, "a".

Example 3: "cbbd"


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

In this example, the longest palindromic substring is "bb". The code will iterate through the string, and when it reaches the character 'b' at index 1, it will call expand_around_center(1, 1) for odd-length palindromes and expand_around_center(1, 2) for even-length palindromes. The call expand_around_center(1, 2) will expand to the substring "bb", updating start and end to represent this longest palindromic substring. The function will then return "bb".

Example 4: "cbbbbd"


Input: s = "cbbbbd"
Output: "bbbb"

In this example, the longest palindromic substring is "bbbb". The code will iterate through the string, and when it reaches the character 'b' at index 2, it will call expand_around_center(2, 2) for odd-length palindromes and expand_around_center(1, 3) for even-length palindromes. The call expand_around_center(1, 3) will expand to the substring "bbbb", updating start and end to represent this longest palindromic substring. The function will then return "bbbb".

Example 5: "acbbbbca"


Input: s = "acbbbbca"
Output: "bbbbb"

In this example, the longest palindromic substring is "bbbbb". The code will iterate through the string, and when it reaches the character 'b' at index 2, it will call expand_around_center(2, 2) for odd-length palindromes and expand_around_center(1, 4) for even-length palindromes. The call expand_around_center(1, 4) will expand to the substring "bbbbb", updating start and end to represent this longest palindromic substring. The function will then return "bbbbb".

Example 6: "acbbbba"


Input: s = "acbbbba"
Output: "bbbbb"

Example 7: "a"


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

In this example, the input string itself is a palindrome of length 1. The code will iterate through the string, calling expand_around_center(0, 0) for the single character 'a'. Since there is no further expansion possible, start and end will be set to 0, and the function will return "a".

Example 8: "caba"


Input: s = "caba"
Output: "aba"

In this example, the longest palindromic substring is "aba". The code will iterate through the string, and when it reaches the character 'a' at index 1, it will call expand_around_center(1, 1) for odd-length palindromes and expand_around_center(1, 2) for even-length palindromes. The call expand_around_center(1, 2) will expand to the substring "aba", updating start and end to represent this longest palindromic substring. The function will then return "aba".

Discussion on Complexity

The time complexity of the "Expand Around Center" approach is O(n^2), where n is the length of the input string. This is because, in the worst case, we need to check each character as a potential center of a palindrome and expand outwards from each center. The space complexity is O(1), as we only use a few additional variables to keep track of the start and end indices of the longest palindromic substring.

While the time complexity of O(n^2) is not optimal, it is still better than the brute force approach, which has a time complexity of O(n^3). Additionally, the "Expand Around Center" approach is a clean and efficient solution that is easy to understand and implement, making it a popular choice for coding interviews.

Conclusion

The "Longest Palindromic Substring" problem is a classic coding challenge that tests problem-solving skills and understanding of string manipulation. By exploring different approaches and settling on the "Expand Around Center" solution, we’ve have demonstrated ability to analyze algorithms and choose an optimal approach.