Longest Palindrome in a string

Dec 18, 2024 • 4 mins read

Problem Overview

The Longest Palindromic Substring problem is a common algorithmic challenge that involves finding the longest contiguous substring within a given string that reads the same backward as forward. Palindromes are often explored in computational problems due to their symmetrical nature which introduces interesting algorithmic challenges.

Understanding the Problem

Given a string s, the task is to identify the longest substring that is a palindrome. For example, in the string "babad", the longest palindromic substring is either "bab" or "aba". Note that there can be multiple correct outputs if the string has more than one palindrome of maximum length.

Constraints:

The length of the string s is at least 1 and can go up to 1000.
The input string contains only ASCII characters.

Key DSA Concepts and Theory

1. Strings

Strings are sequences of characters, commonly used in computer science and programming to represent text. They offer various operations for manipulation, comparison, and searching, making them an essential concept for solving many types of algorithmic problems.

2. Palindrome

A palindrome is a word, phrase, or sequence that reads the same backward as forward. The property of symmetry in palindromes is leveraged when designing algorithms to identify or generate such sequences.

3. Dynamic Programming

Dynamic programming (DP) is a method for solving problems by breaking them down into subproblems. It is particularly useful when a problem has overlapping subproblems and optimal substructure. For palindromic substrings, DP can be used to store previously calculated palindromic states to optimize the overall computation.

Solution Approach

Expand Around Center Approach

One intuitive approach to solve this problem is to expand around each possible center of the palindrome. For each character in the string, consider it as the center of a potential palindrome and expand outward while checking for palindrome validity.

Steps:

Iterate through each character in the string.
For each character, expand around it to check odd-length and even-length palindromes.
Keep track of the maximum length palindrome found during these expansions.
Return the longest palindromic substring identified.

This approach has a time complexity of O(n^2), which is efficient enough given the problem constraints.

Code Examples

C++

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int start = 0, end = 0;
        
        for (int i = 0; i < s.size(); i++) {
            // Odd length palindromes
            int len1 = expandAroundCenter(s, i, i);
            // Even length palindromes
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = max(len1, len2);
            if (len > (end - start)) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }
    
private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

Java

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Odd length palindromes
            int len1 = expandAroundCenter(s, i, i);
            // Even length palindromes
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = Math.max(len1, len2);
            if (len > (end - start)) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n^2) - The function expandAroundCenter is called for each character in the string and expands to both left and right directions.
Space Complexity: O(1) - No additional space proportional to the input size is used, aside from a few integer variables for tracking indices and lengths.

Common Mistakes to Avoid

Forgetting to check for odd and even length palindromes separately.
Incorrectly calculating the indices when attempting to extract the substring from the original string.

Additional Resources and References

Books on algorithms and data structures for understanding dynamic programming in greater depth, such as "Introduction to Algorithms" by Cormen et al.
Online algorithm courses that cover string manipulation and palindrome problems.