Shortest palindrome

String Rolling Hash String Matching Hash Function

42.0% acceptance

Jan 12, 2026

4549

293

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_palindrome(s: String) -> String {
    if s.is_empty() { return s; }
    
    let rev: String = s.chars().rev().collect();
    let combined = format!("{}#{}", s, rev);
    let lps = Self::compute_lps(&combined);
    
    let to_add = s.len() - lps[combined.len() - 1];
    let prefix: String = s.chars().rev().take(to_add).collect();
    format!("{}{}", prefix, s)
  }
  
  fn compute_lps(s: &str) -> Vec<usize> {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    let mut lps = vec![0; n];
    let mut len = 0;
    let mut i = 1;
    
    while i < n {
      if chars[i] == chars[len] {
        len += 1;
        lps[i] = len;
        i += 1;
      } else {
        if len != 0 {
          len = lps[len - 1];
        } else {
          lps[i] = 0;
          i += 1;
        }
      }
    }
    lps
  }
}