Solving Longest Palindromic Substring: A Multi-Language Approach

leetcodetypescriptrubypythoncoding-interview

The Longest Palindromic Substring problem is a classic algorithmic challenge that tests your understanding of string manipulation and dynamic programming. Let's solve it in multiple programming languages and explore different approaches.

Problem Statement

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

Example 1:

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

Example 2:

text
1Input: s = "cbbd"
2Output: "bb"

Understanding the Problem

A palindrome is a string that reads the same forward and backward. The challenge is to find the longest such substring within a given string. There are several approaches to solve this:

  1. Brute Force (O(n³))
  2. Dynamic Programming (O(n²))
  3. Expand Around Center (O(n²))
  4. Manacher's Algorithm (O(n)) - advanced

We'll implement the "Expand Around Center" approach as it's both efficient and intuitive.

TypeScript Implementation

typescript
1function longestPalindrome(s: string): string {
2    if (s.length < 2) return s;
3    
4    let start = 0;
5    let maxLength = 1;
6    
7    function expandAroundCenter(left: number, right: number): void {
8        while (left >= 0 && right < s.length && s[left] === s[right]) {
9            const currentLength = right - left + 1;
10            if (currentLength > maxLength) {
11                start = left;
12                maxLength = currentLength;
13            }
14            left--;
15            right++;
16        }
17    }
18    
19    for (let i = 0; i < s.length; i++) {
20        expandAroundCenter(i, i);     // Odd length palindromes
21        expandAroundCenter(i, i + 1); // Even length palindromes
22    }
23    
24    return s.substring(start, start + maxLength);
25}
26

27// Example usage
28console.log(longestPalindrome("babad")); // "bab"
29console.log(longestPalindrome("cbbd"));  // "bb"

Ruby Implementation

ruby
1def longest_palindrome(s)
2    return s if s.length < 2
3    
4    start = 0
5    max_length = 1
6    
7    def expand_around_center(s, left, right, start, max_length)
8        while left >= 0 && right < s.length && s[left] == s[right]
9            current_length = right - left + 1
10            if current_length > max_length
11                start[0] = left
12                max_length[0] = current_length
13            end
14            left -= 1
15            right += 1
16        end
17    end
18    
19    start_ref = [start]
20    max_length_ref = [max_length]
21    
22    (0...s.length).each do |i|
23        expand_around_center(s, i, i, start_ref, max_length_ref)     # Odd length
24        expand_around_center(s, i, i + 1, start_ref, max_length_ref) # Even length
25    end
26    
27    s[start_ref[0], max_length_ref[0]]
28end
29

30# Example usage
31puts longest_palindrome("babad") # "bab"
32puts longest_palindrome("cbbd")  # "bb"

Python Implementation

python
1def longest_palindrome(s: str) -> str:
2    if len(s) < 2:
3        return s
4    
5    start = 0
6    max_length = 1
7    
8    def expand_around_center(left: int, right: int) -> None:
9        nonlocal start, max_length
10        
11        while left >= 0 and right < len(s) and s[left] == s[right]:
12            current_length = right - left + 1
13            if current_length > max_length:
14                start = left
15                max_length = current_length
16            left -= 1
17            right += 1
18    
19    for i in range(len(s)):
20        expand_around_center(i, i)     # Odd length palindromes
21        expand_around_center(i, i + 1) # Even length palindromes
22    
23    return s[start:start + max_length]
24

25# Example usage
26print(longest_palindrome("babad"))  # "bab"
27print(longest_palindrome("cbbd"))   # "bb"

Code Walkthrough

Let's break down the key components of our solution:

  1. Base Case

    • If string length is less than 2, return the string itself
    • A single character is always a palindrome

  2. Expand Around Center Function

    • Takes left and right pointers as parameters
    • Expands outward while characters match
    • Updates global tracking of longest palindrome found

  3. Main Loop

    • Iterates through each character
    • Checks for both odd and even length palindromes
    • Uses two separate expansions for each position

  4. Time and Space Complexity

    • Time Complexity: O(n²)
    • Space Complexity: O(1)

Performance Optimization Tips

  1. Early Termination

    • If remaining string length is less than current max, stop searching
    • Implement bounds checking before expansion

  2. Memory Management

    • TypeScript/JavaScript: Use substring instead of slice
    • Python: Use string slicing efficiently
    • Ruby: Use proper string range operations

  3. Language-Specific Optimizations

    • TypeScript: Use type annotations for better performance
    • Python: Consider using memoryview for large strings
    • Ruby: Use frozen string literals when possible

Related Problems

  • Palindromic Substrings (LeetCode 647)
  • Valid Palindrome (LeetCode 125)
  • Palindrome Pairs (LeetCode 336)

Related Resources

Conclusion

The Longest Palindromic Substring problem demonstrates the importance of efficient algorithm design and language-specific implementations. While the core logic remains similar across languages, each implementation takes advantage of language-specific features for optimal performance.

Remember to practice this problem with different input sizes and edge cases to fully understand its complexity and optimization opportunities.

Suggested Articles

Climbing Stairs LeetCode Solution in JavaScript and TypeScript

2024-12-17leetcodetypescriptdynamic-programmingalgorithmscoding-interviewjavascriptfibonacci

Valid Parentheses LeetCode Solution in JavaScript and TypeScript

2024-12-17leetcodetypescriptjavascriptstackalgorithmscoding-interviewstring-manipulationdata-structures

JWT Authentication in Node.js and TypeScript: Modern Web Development Guide

2024-12-09nodejstypescriptjwtauthenticationsecurity