Leetcode problem help: longest_palindrome

Hi folks, I come from the front end world and I've done this LC problem in JS. I translated it into rust, and for some reason rust is performing much worse than JS (122ms vs 1998ms). I'm not sure where the problem lies and would like to learn why this is the case.

use std::cmp;

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let (mut start, mut end) = (0, 0);
        for i in 0..s.len() {
            let odd_expand = Solution::expand(&s, i, i);
            let even_expand = Solution::expand(&s, i, i + 1);
            let len = cmp::max(odd_expand, even_expand);
            if len > end - start {
                start = i - (len - 1) / 2;
                end = i + (len / 2);
            }
        }
        s[start..=end].to_string()
    }

    fn expand(s: &str, left: usize, right: usize) -> usize {
        let (mut l, mut r) = (left as i32, right as i32);
        let len = s.len() as i32;
        while l >= 0 && r < len && s.chars().nth(l as usize).unwrap() == s.chars().nth(r as usize).unwrap() {
            l -= 1;
            r += 1;
        }
        (r - l - 1_i32) as usize
    }
}

EDIT: Attached is the JS solution

var longestPalindrome = function(s) {
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    let len1 = expand(s, i, i);
    let len2 = expand(s, i, i + 1);
    let len = Math.max(len1, len2);
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len/2);
    }
  }
  return s.slice(start, end + 1);
}

function expand(s, left, right) {
  let l = left, r = right;
  while (l >= 0 && r < s.length && s[l] == s[r]) {
    l--;
    r++;
  }
  return r - l - 1;
}

With zero context (because you aren't providing the Javascript solution to compare against) here's a possible guess: you are using .chars().nth(…) which is a linear time algorithm seeking to the nth unicode character in a UTF-8 string, whereas the easiest indexing solutions in JS would probably index straight into the UTF-16 code units that make up Javascript's string type, as far as I'm aware.[1] If this is the significant difference here, it wouldn't be surprising why your Rust code is at a disadvantage, especially in case of long strings.


  1. By which I mean, as someone largely unfamiliar with Javascript, that that's going as far as I could find out by googling for what JS strings are like and how they can be indexed. ↩︎

5 Likes

Thanks, it looks like you are correct. s.chars().nth(l) looks like the bottleneck. 1998ms is down to <3ms when I changed the line to:

while l >= 0 && r < len && s.as_bytes()[l as usize] == s.as_bytes()[r as usize] {

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.