Finding the Longest Palindromic Substring in Rust

Palindromes are fascinating patterns in strings that read the same backward as forward. Among the various problems in string manipulation, one classic challenge is finding the longest palindromic substring in a given string. In this article, we’ll explore an efficient solution using the Expand Around Center technique in Rust.

Problem Statement

Input: A string s containing letters, digits, or special characters.

Output: The longest substring of s that is a palindrome.

Example 1:

Input: "babad"
Output: "aba" or "bab"

Example 2:

Input: "cbbd"
Output: "bb"

Constraints

1. The string length n can range from 1 to 1000.
2. The input string contains only printable ASCII characters.

Approach: Expand Around Center

The idea behind the Expand Around Center approach is simple: Every palindrome has a center, and we can expand outward from that center to check for palindromic properties. For example:

• A single character is always a palindrome (odd-length palindrome).
• Two identical adjacent characters form the base of an even-length palindrome.

Steps to Solve

Expand Around Potential Centers:

• Treat every character as a center for odd-length palindromes.
• Treat every pair of adjacent identical characters as a center for even-length palindromes.

Track the Longest Palindrome:

• For each center, expand outward while the left and right characters match.
• Update the starting index and length of the longest palindrome when a new maximum is found.

Edge Cases:

• If the input string has a length of 0 or 1, it is already a palindrome.
• Handle edge cases where expansions may go out of bounds.

Rust Implementation

Here is the complete implementation of the Expand Around Center approach in Rust:

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let n = s.len();
        if n < 2 {
            return s; // If the string is empty or has one character, it is already a palindrome.
        }
        let s_chars: Vec<char> = s.chars().collect(); // Convert the string to a character vector.
        let mut start = 0; // Start index of the longest palindrome.
        let mut max_len = 0; // Maximum length of the longest palindrome.
        // Helper function to expand around a center.
        let expand = |mut left: usize, mut right: usize| -> (usize, usize) {
            while left > 0 && right < n && s_chars[left] == s_chars[right] {
                left -= 1;
                right += 1;
            }
            (left, right)
        };
        for i in 0..n {
            // Check for odd-length palindrome (single center).
            let (l1, r1) = expand(i, i);
            if r1 - l1 - 1 > max_len {
                max_len = r1 - l1 - 1;
                start = l1 + 1;
            }
            // Check for even-length palindrome (double center).
            if i + 1 < n && s_chars[i] == s_chars[i + 1] {
                let (l2, r2) = expand(i, i + 1);
                if r2 - l2 - 1 > max_len {
                    max_len = r2 - l2 - 1;
                    start = l2 + 1;
                }
            }
        }
        s[start..start + max_len].to_string()
    }
}

How the Code Works

1. Initialization

• Convert the input string s into a Vec<char> to easily access individual characters using indices.
• Initialize start to track the starting index of the longest palindrome and max_len to track its length.

2. Expand Around Centers

• The function expand takes two indices (left and right) and expands outward as long as the characters at these indices are equal.
• This checks both odd-length and even-length palindromes.

3. Track the Longest Palindrome

• For every character, attempt to expand for both odd-length and even-length palindromes.
• Update start and max_len if a longer palindrome is found during the expansion.

4. Edge Cases

• Single-character strings are already palindromes.
• The expand function ensures expansions don’t go out of bounds.

Complexity Analysis

Time Complexity:

• For every character, we attempt to expand outward. Each expansion takes linear time relative to the length of the palindrome.
• Total time complexity: O(n²).

Space Complexity:

• The solution uses a Vec<char> to store the characters of the string, which takes O(n) space.
• No additional auxiliary structures are used, making it more space-efficient than a Dynamic Programming approach.

Example Walkthrough

Example Input:

let s = "babad".to_string();

Execution Steps:

Initialization:

• start = 0, max_len = 0.

Iteration:

• For i = 0: Expand around "b". Longest palindrome: "b". Update start = 0, max_len = 1.
• For i = 1: Expand around "a". Longest palindrome: "aba". Update start = 0, max_len = 3.
• For i = 2: Expand around "b". Longest palindrome: "bab". No updates as length is equal to the current max length.
• For i = 3: Expand around "a". Longest palindrome: "a".
• For i = 4: Expand around "d". Longest palindrome: "d".

Final Result:

• The longest palindrome is "aba".

Output:

"aba"

Advantages of the Expand Around Center Approach

Simpler Logic

• Avoids complex data structures like 2D arrays (used in Dynamic Programming).
• Handles odd and even palindromes naturally with minimal additional logic.

Space Efficiency:

• Only uses linear space, making it more practical for large inputs compared to the quadratic space requirements of DP.

Performance:

• While the time complexity is the same as DP, this approach is often faster in practice due to fewer memory operations.

Conclusion

The Expand Around Center approach is an elegant and efficient way to solve the problem of finding the longest palindromic substring. It balances simplicity and performance, making it a great choice for interviews and practical applications. The provided Rust implementation showcases the power of Rust’s safety and performance guarantees while solving a classic algorithmic problem.