Longest Palindromic Substring Algorithm Solution

The longest palindromic substring problem requires identifying the longest contiguous sequence that reads the same forwards and backwards. This solution implements an efficient expand-around-centers approach with O(n²) time complexity and O(1) space complexity.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected time complexity constraint? (e.g., O(n²) vs O(n log n) vs O(n))
2. Can we modify the input string, or must we work with a copy?
3. Are we guaranteed that the input will contain at least one character?
4. Should we return the actual substring or just its length and indices?
5. How large can the input string be (e.g., up to 10⁴, 10⁶ characters)?

Restated problem in my own words: Given a string, find the longest contiguous substring that reads the same forwards and backwards (a palindrome). If multiple palindromes exist with the same maximum length, return any one of them.

Input/output specification:

• Input: A string s of length n (1 ≤ n ≤ 1000)
• Output: The longest palindromic substring of s
• Assumption: The string contains only printable ASCII characters

Key constraints and assumptions:

• We're looking for contiguous substrings (not subsequences)
• The input string can contain any printable ASCII character
• If there are multiple longest palindromes, we can return any one
• The solution should handle edge cases like empty string or single character (which are themselves palindromes)
• We can modify the input string if needed, but it's safer to work with a copy

Data shape and hidden structure: The problem involves identifying symmetric properties within character sequences. The key insight is that every palindrome has a center point (either a single character for odd-length palindromes, or between two characters for even-length palindromes). This suggests we can use a "center expansion" approach where we test each possible center and expand outward while maintaining symmetry.

The structure is inherently symmetric — for any valid palindrome, the characters equidistant from the center must match. This symmetry property is fundamental to our approach and allows us to optimize checking for palindromes by only expanding from potential centers rather than checking all substrings.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern for this problem is Expand Around Centers. This approach leverages the fundamental property that every palindrome has a center - either a single character (for odd-length palindromes) or between two characters (for even-length palindromes).

Wording that signals the pattern

The problem statement "Longest Palindromic Substring" contains key indicators:

• "Palindromic" - the core structure we're looking for
• "Substring" - continuous sequence that can be analyzed from centers
• "Longest" - optimization goal requiring us to check multiple candidates

Why this problem fits the pattern

This problem fits the expand around centers pattern because:

1. Palindromes are symmetric around their center
2. We can systematically test each possible center position
3. For each center, we expand outward while characters match
4. This naturally handles both odd and even length palindromes by treating each character and each gap between characters as potential centers

Core insight needed to solve it

The key insight is that we don't need to check all possible substrings (which would be O(n³)). Instead, we can observe that every palindrome has a unique center. By expanding from each possible center position (both single characters and gaps between characters), we can find all palindromes in O(n²) time while maintaining correctness.

This approach reduces the problem from checking all substrings to checking only O(n) candidate centers, each expanded up to O(n) length.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every possible substring to see if it's a palindrome, but that would be O(n³) time complexity because we have O(n²) substrings and O(n) time to check each palindrome. Let me think about how to optimize this.

I notice that if I expand around potential centers, I can reduce the complexity significantly. Since a palindrome can have either odd or even length, I need to consider both cases - each character as a center for odd-length palindromes and each pair of adjacent characters as centers for even-length palindromes.

The key insight is that instead of checking all substrings, I can expand outward from each potential center and stop expanding as soon as the characters don't match. This way, I only do O(n) work per center, and since there are at most 2n potential centers (n odd-length centers and n even-length centers), the overall complexity becomes O(n²).

Let me think about invariants that must hold:

1. When expanding from a center, I maintain the property that all characters at equal distance from center are identical
2. The algorithm must handle both odd and even length palindromes correctly
3. I need to track the longest palindrome found so far

The most efficient approach is to iterate through each possible center position and expand outward, keeping track of the maximum length found. This is O(n²) time and O(1) space, which is optimal for this problem since we must examine at least some characters to determine the answer.

For each character position i:

• Expand around center i (odd-length palindromes)
• Expand around centers i and i+1 (even-length palindromes)
• Keep track of the longest palindrome found

This approach is optimal because:

1. We can't do better than O(n²) since in worst case, we might need to output the entire string as a palindrome
2. We only make one pass through the string with constant-time operations at each step
3. The expansion stops early when characters don't match, avoiding unnecessary checks

4. Data Structure Choice

For this problem, I'll use a combination of:

1. String/char array - to represent the input and allow efficient character access
2. Two pointers (integers) - to track the current palindrome bounds during expansion
3. Integer variables - to maintain the maximum length found and its starting position

Why This Choice Works

The key insight is that we don't need complex data structures like hash maps or trees. The problem asks for the longest palindromic substring, which can be efficiently found by expanding around potential centers.

The string itself serves as our primary data structure - we can access any character in O(1) time and expand outward from any position. The two pointers (left and right indices) are sufficient to track the current bounds of our palindrome expansion.

Space Considerations

We only use O(1) extra space beyond the input string (just a few integer variables to track indices and max length). This is optimal since we're not required to store intermediate results or build auxiliary structures.

Helper Structures

We don't need any helper data structures beyond basic variables. The algorithm naturally works by maintaining invariants:

• We expand from center positions (odd and even length palindromes)
• We keep track of the maximum palindrome found so far
• We use simple integer indices to avoid creating new string objects

This approach is memory-efficient and avoids unnecessary object creation that would occur with substring operations.

Trade-offs

Alternative approaches like storing all palindromes in a map or using dynamic programming tables would require O(n²) space, which is wasteful for this problem. The two-pointer approach with expansion gives us the optimal O(1) space complexity while maintaining O(n) time performance.

5. Algorithm Walkthrough

Let me trace through the algorithm with the example input "babad":

Step 1: Initialize start = 0, maxLen = 1

Step 2: Process each character as potential center:

• i=0: center at 'b'
  • Expand around center: left=0, right=0
  • Palindrome length = 1, maxLen still 1
• i=1: center at 'a'
  • Expand around center: left=0, right=2 (substring "bab")
  • Palindrome length = 3, update maxLen = 3, start = 0
• i=2: center at 'b'
  • Expand around center: left=1, right=3 (substring "aba")
  • Palindrome length = 3, maxLen still 3, start = 0
• i=3: center at 'a'
  • Expand around center: left=2, right=4 (substring "bad")
  • Palindrome length = 1, maxLen still 3
• i=4: center at 'd'
  • Expand around center: left=4, right=4
  • Palindrome length = 1, maxLen still 3

Step 3: Return substring from index start to start + maxLen = "bab"

Key observations:

• We handle both odd-length palindromes (single character center) and even-length palindromes (between two characters)
• For each position, we expand outward while characters match
• We track the global maximum to ensure we find the longest overall palindrome
• The algorithm correctly identifies "bab" as the longest palindromic substring

Edge case handling:

• Single character input returns that character
• Even-length inputs with no palindromes > 1 return first character
• The expansion logic naturally handles boundary conditions by checking bounds

6. Java Solution

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int start = 0;
        int maxLength = 1;
        
        // For each possible center position
        for (int i = 0; i < s.length(); i++) {
            // Check for odd-length palindromes (center at i)
            int len1 = expandAroundCenter(s, i, i);
            // Check for even-length palindromes (center between i and i+1)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            // Get the maximum length palindrome centered at position i
            int currentMax = Math.max(len1, len2);
            
            // Update global maximum if we found a longer palindrome
            if (currentMax > maxLength) {
                maxLength = currentMax;
                // Calculate the starting position of this palindrome
                start = i - (currentMax - 1) / 2;
            }
        }
        
        return s.substring(start, start + maxLength);
    }
    
    /**
     * Expands around the center defined by left and right indices
     * Returns the length of the palindrome found
     */
    private int expandAroundCenter(String s, int left, int right) {
        // Expand outward while characters match and indices are valid
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        
        // Return the length of palindrome (right - left - 1)
        // We subtract 1 because we overcounted by one extra expansion
        return right - left - 1;
    }
}

This solution uses the "expand around center" approach. For each possible center position (both single character centers and between-character centers), we expand outward while the characters match, keeping track of the longest palindrome found so far. The key insight is that every palindrome has a unique center, and by checking all possible centers, we can find the longest one.

7. Complexity Analysis

Time Complexity: O(n²)

The algorithm uses the expand-around-centers approach where we iterate through each possible center position (both odd and even length palindromes). For each center, we potentially expand up to n/2 characters in both directions. Since we have at most 2n centers to check (n odd-length and n even-length), and each expansion can take O(n) time in the worst case, the overall time complexity is O(n²).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables like left, right, maxLen, and start. No additional data structures that grow with input size are used, making the space complexity O(1).

Why these bounds are correct:

The time analysis considers that we check at most 2n centers, and for each center, the expansion can go up to n/2 characters in each direction. However, this is not a tight bound since not all expansions reach the maximum length. In practice, once we find a palindrome of length k, we can skip centers that would produce palindromes shorter than our current maximum. But in the worst case where all characters are the same, we do need to check all centers and expand fully.

The space complexity is constant because we only maintain a few integer variables regardless of input size, and we don't use any data structures that grow with the input.

Optimality:

This solution is optimal for the given constraints where we must return the actual longest palindromic substring rather than just its length. The O(n²) time complexity is the best we can achieve for this specific problem because we must potentially examine each character in relation to others to determine palindromic properties. There are O(n²) possible substrings, and checking each for palindrome property would be O(n³), but our approach avoids redundant checks by expanding from centers rather than generating all substrings.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Returns empty string (edge case that must be handled explicitly)
• Single character: Returns that character (trivial palindrome)
• Two characters: Returns the longer palindromic substring if both characters are equal

Duplicate Values and Repeated States

• All identical characters: Algorithm must correctly identify the entire string as a palindrome
• Multiple palindromes of same length: Algorithm should return any valid longest palindrome (implementation-dependent)
• Overlapping palindromes: The center expansion approach correctly handles nested palindromes

Boundary Conditions

• String with length 1: Trivial case that must be handled
• String with length 2: Must check both single character and two-character palindromes
• String at maximum constraints: For very large strings (e.g., 10^5 characters), ensure O(n²) approach doesn't cause timeouts

Common Implementation Mistakes

• Off-by-one errors in expansion: When expanding from center, ensure bounds checking prevents array index out of bounds
• Incorrect palindrome length handling: Mismanaging odd vs even length palindromes can cause incorrect results
• Not resetting max variables: When tracking longest palindrome, ensure proper reset of max length and indices
• Failing to handle even-length palindromes: The algorithm must check both odd and even length cases by treating each character as a potential center
• Using wrong indices: When updating result indices, ensure they correctly map to the original string positions

Implementation-specific Pitfalls

• Not accounting for both center types: Failing to check palindromes centered at each character (odd-length) and between characters (even-length)
• Integer overflow in indices: Though unlikely with typical constraints, ensure index calculations don't overflow
• Inefficient string slicing: Avoid creating substring copies in inner loops; work with indices instead

9. Alternative Approaches

There are several alternative approaches to solving the longest palindromic substring problem, each with different trade-offs:

1. Expand Around Centers Approach: Instead of using a 2D DP table, we can expand around each possible center position. For each character (for odd-length palindromes) and each pair of adjacent characters (for even-length palindromes), we expand outward while characters match. This approach has O(1) space complexity but still requires O(n²) time in the worst case. It's more intuitive and uses less space than the full DP solution.

2. Manacher's Algorithm: This is a sophisticated linear-time algorithm that uses the concept of "palindromic radius" and the symmetry property of palindromes. It maintains a "rightmost palindrome" boundary and uses previously computed information to avoid redundant comparisons. This approach achieves O(n) time complexity but is significantly more complex to implement correctly and understand.

3. Suffix Array/Tree Approach: We could build a suffix array or suffix tree of the string and search for palindromes by checking if substrings are equal to their reverses. This approach has O(n log n) or O(n) time complexity depending on implementation but requires more complex data structures and is overkill for this specific problem.

The chosen solution (2D Dynamic Programming) is preferred in interviews because it's clean, readable, and demonstrates solid understanding of DP principles. The expand-around-centers approach is more space-efficient and intuitive, while Manacher's algorithm is optimal but much harder to implement correctly under time constraints.

10. Test Cases

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem
        assert longestPalindrome("babad").equals("bab") || longestPalindrome("babad").equals("aba");
        
        // Test case 2: Even length palindrome
        assert longestPalindrome("cbbd").equals("bb");
        
        // Test case 3: Single character
        assert longestPalindrome("a").equals("a");
        
        // Test case 4: Empty string
        assert longestPalindrome("").equals("");
        
        // Test case 5: All same characters
        assert longestPalindrome("aaaa").equals("aaaa");
        
        // Test case 6: No palindrome longer than 1
        assert longestPalindrome("abc").equals("a") || longestPalindrome("abc").equals("b") || longestPalindrome("abc").equals("c");
        
        // Test case 7: Complex case with multiple palindromes
        assert longestPalindrome("abacabad").equals("abacaba");
        
        // Test case 8: Palindrome at end
        assert longestPalindrome("abcdefedcba").equals("abcdefedcba");
        
        // Test case 9: Palindrome at beginning
        assert longestPalindrome("racecarxyz").equals("racecar");
        
        // Test case 10: Large string with multiple candidates
        String large = "abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba";
        assert longestPalindrome(large).equals("a");
        
        System.out.println("All test cases passed!");
    }
    
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0, maxLength = 1;
        
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            
            if (len > maxLength) {
                maxLength = len;
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substring(start, start + maxLength);
    }
    
    private static 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;
    }
}

The test cases cover:

• Basic functionality with odd and even length palindromes
• Edge cases like empty string and single character
• Boundary conditions with all same characters
• Cases where no palindrome longer than 1 exists
• Complex scenarios with multiple potential palindromes
• Strings where the longest palindrome appears at string boundaries

Each test validates that the solution correctly identifies the longest palindromic substring, handling both odd and even length cases properly.

11. Final Summary

The core insight is that we can expand around potential palindrome centers to efficiently find the longest palindromic substring in linear time. By treating each character (and pair of characters) as a potential center and expanding outward while maintaining the palindrome property, we achieve an optimal O(n) time complexity. This approach works because every palindrome has a unique center, and we only need to check at most one expansion per center. The solution is both time and space optimal for this problem, making it ideal for FAANG-level systems where performance and correctness are paramount.