Solving Longest Palindromic Substring: A Multi-Language Approach

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. For more on string manipulation, check out our guide on memoization in ruby for optimization.

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. For more on performance optimization, see our guide on performance bottlenecks in rails applications.

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

For more on Ruby optimization techniques, check out our guide on memoization in ruby performance improvement.

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. For more on code optimization, see our guide on optimize large lists tables rendering performance.

  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

For more on performance optimization, check out our guide on optimize database queries rails application.

  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

Threading Considerations

When implementing this in a web application, consider threading implications. For more details, see our guide on multithreading vs multiprocessing in ruby.

Related Problems

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

Related Resources

Performance and Optimization

Implementation and Best Practices

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. For more on optimizing Ruby applications, check out our guide on optimize rails app for high traffic.

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

Suggested Articles