Longest palindromic substring

Two Pointers String Dynamic Programming

37.4% acceptance

Jan 12, 2026

32411

1994

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

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_palindrome(s: String) -> String {
    if s.is_empty() {
      return String::new();
    }
    
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut start = 0;
    let mut max_len = 1;
    
    // Helper function to expand around center
    fn expand_around_center(s: &[u8], mut left: i32, mut right: i32) -> usize {
      while left >= 0 && (right as usize) < s.len() && s[left as usize] == s[right as usize] {
        left -= 1;
        right += 1;
      }
      (right - left - 1) as usize
    }
    
    for i in 0..n {
      // Odd length palindromes (center is a single character)
      let len1 = expand_around_center(bytes, i as i32, i as i32);
      // Even length palindromes (center is between two characters)
      let len2 = expand_around_center(bytes, i as i32, (i + 1) as i32);
      
      let len = len1.max(len2);
      
      if len > max_len {
        max_len = len;
        start = i - (len - 1) / 2;
      }
    }
    
    s[start..start + max_len].to_string()
  }
}