Claude vs Perplexity for Coding

Longest Palindromic Substring

I'll implement this using the Expand Around Center approach, which is intuitive and efficient.

Implementation

def longest_palindromic_substring(s: str) -> str:
    """
    Find the longest palindromic substring using the Expand Around Center approach.
    
    Args:
        s: Input string
        
    Returns:
        The longest palindromic substring
        
    Examples:
        >>> longest_palindromic_substring("babad")
        'bab'
        >>> longest_palindromic_substring("cbbd")
        'bb'
        >>> longest_palindromic_substring("racecar")
        'racecar'
    """
    if not s:
        return ""
    
    # Track the start index and max length of the longest palindrome found
    start = 0
    max_length = 1  # Single character is always a palindrome
    
    def expand_around_center(left: int, right: int) -> tuple[int, int]:
        """
        Expand outward from center while characters match.
        Handles both odd-length (single center) and even-length (double center) palindromes.
        
        Returns:
            Tuple of (start_index, length) of the palindrome found
        """
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        
        # After the loop, left and right are one step BEYOND the palindrome
        palindrome_start = left + 1
        palindrome_length = right - left - 1
        return palindrome_start, palindrome_length
    
    for i in range(len(s)):
        # Case 1: Odd-length palindrome (e.g., "aba") — single character center
        odd_start, odd_length = expand_around_center(i, i)
        
        # Case 2: Even-length palindrome (e.g., "abba") — two character center
        even_start, even_length = expand_around_center(i, i + 1)
        
        # Update best palindrome found
        if odd_length > max_length:
            max_length = odd_length
            start = odd_start
        
        if even_length > max_length:
            max_length = even_length
            start = even_start
    
    return s[start : start + max_length]


def longest_palindromic_substring_dp(s: str) -> str:
    """
    Alternative: Dynamic Programming approach.
    dp[i][j] = True if s[i..j] is a palindrome.
    
    Time Complexity:  O(n²)
    Space Complexity: O(n²)
    """
    if not s:
        return ""
    
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1
    
    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True
    
    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_length = i, 2
    
    # Check substrings of length 3 and greater
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1  # Ending index
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_length:
                    start, max_length = i, length
    
    return s[start : start + max_length]


# ── Tests ──────────────────────────────────────────────────────────────────────

def run_tests():
    test_cases = [
        # (input, expected_length, description)
        ("babad",   3, "Classic example — 'bab' or 'aba'"),
        ("cbbd",    2, "Even palindrome — 'bb'"),
        ("racecar", 7, "Entire string is a palindrome"),
        ("a",       1, "Single character"),
        ("ac",      1, "No palindrome longer than 1"),
        ("",        0, "Empty string"),
        ("aaaa",    4, "All same characters"),
        ("abacaba", 7, "Entire string — odd length"),
        ("xyzabacabazyx", 13, "Long palindrome"),
    ]
    
    print(f"{'Input':<20} {'Expected Len':<15} {'Result':<20} {'Status'}")
    print("-" * 70)
    
    all_passed = True
    for s, expected_len, description in test_cases:
        result = longest_palindromic_substring(s)
        result_dp = longest_palindromic_substring_dp(s)
        
        # Verify result IS a palindrome and has the correct length
        is_palindrome = result == result[::-1]
        length_correct = len(result) == expected_len
        dp_matches = len(result_dp) == expected_len
        
        status = "✅ PASS" if (is_palindrome and length_correct and dp_matches) else "❌ FAIL"
        if "FAIL" in status:
            all_passed = False
        
        print(f"{repr(s):<20} {expected_len:<15} {repr(result):<20} {status}")
        if "FAIL" in status:
            print(f"  → Got length {len(result)}, is_palindrome={is_palindrome}")
    
    print("-" * 70)
    print(f"All tests passed: {all_passed}")

run_tests()

Sample Output

Input                Expected Len    Result               Status
----------------------------------------------------------------------
'babad'              3               'bab'                ✅ PASS
'cbbd'               2               'bb'                 ✅ PASS
'racecar'            7               'racecar'            ✅ PASS
'a'                  1               'a'                  ✅ PASS
'ac'                 1               'a'                  ✅ PASS
''                   0               ''                   ✅ PASS
'aaaa'               4               'aaaa'               ✅ PASS
'abacaba'            7               'abacaba'            ✅ PASS
'xyzabacabazyx'      13              'xyzabacabazyx'      ✅ PASS
----------------------------------------------------------------------
All tests passed: True

---

Complexity Analysis

Expand Around Center (Primary Approach)

Dimension	Complexity	Reason
Time	O(n²)	n centers × up to n/2 expansions each
Space	O(1)	Only stores index pointers

Dynamic Programming (Alternative)

Dimension	Complexity	Reason
Time	O(n²)	Fill an n×n table
Space	O(n²)	Stores the full DP table

Why Expand Around Center wins in practice

String: "racecar" (n = 7)

Centers checked:
  i=0: 'r'      → expands to "r"        (len 1)
  i=1: 'a'      → expands to "a"        (len 1)
  i=2: 'c'      → expands to "c"        (len 1)
  i=3: 'e'      → expands to "racecar"  (len 7) ✓ WINNER
  ...

Each center: O(n) worst case → Total: O(n) centers × O(n) = O(n²)
Space: Only (start, max_length) tracked → O(1)

Can we do better?

Yes — Manacher's Algorithm solves this in O(n) time and O(n) space by reusing previously computed palindrome information. However, it's significantly more complex to implement and rarely needed in practice.

def longest_palindromic_substring(s: str) -> str:
    """
    Finds the longest palindromic substring using dynamic programming.
    
    Args:
    s: Input string
    
    Returns:
    The longest palindromic substring
    """
    n = len(s)
    if n == 0:
        return ""
    
    # dp[i][j] is True if substring s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]
    
    # All single characters are palindromes
    start = 0
    max_length = 1
    
    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2
    
    # Check substrings of length 3 and longer
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_length = length
    
    return s[start:start + max_length]

Time Complexity Analysis

Time Complexity: O(n²) where n is the length of the input string.[1][2]

Space Complexity: O(n²) for the DP table.[1][2]

Why O(n²) time?

• Initialization: All single characters: O(n)
• Length 2 substrings: O(n) comparisons
• Longer substrings: For each possible length (3 to n) and each starting position, we check one condition: O(n × n) = O(n²)
• Each substring is checked exactly once using previously computed results

DP Table Filling Order

Length 1: dp[i][i] = True for all i
Length 2: Check adjacent pairs only  
Length ≥3: Check s[i]==s[j] AND dp[i+1][j-1]

Example trace for "babad":

i\j 0 1 2 3
0   T F T F    # "b","a","aba"
1     T F T    # "a","ba","aba" 
2       T F    # "b","ad"
3         T    # "d"
Max palindrome: "bab" or "aba" (length 3)

This approach correctly handles all edge cases (empty string, single character, all identical characters) and guarantees finding the longest palindromic substring.[1][2]