fast_longest_palindromic_substring.rs

// @robertkingnz
// this rust implementation reduces the number of centers that need checking
// it does so by only trying one possible center for each group of repeating characters.
// this is one of the few 0ms solutions on leetcode,
// although there is a faster, more complex, O(N) solution possible.

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let b = s.as_bytes();
        fn expand(mut i: usize, mut j: usize, b: &[u8]) -> (usize, usize) {
            while i > 0 && j + 1 < b.len() {
                if b[i-1] == b[j+1] {
                    i -= 1;
                    j += 1;
                } else {
                    break;
                }
            }
            return (i, j-i+1);
        }
        let mut bst = 1usize;
        let mut start = 0usize;
        let mut c = 0usize;
        while c < s.len() {
            let mut i = c;
            while i > 0 && b[i-1] == b[i] {
                i -= 1;
            }
            let mut j = c;
            while j + 1 < b.len() && b[j] == b[j+1] {
                j += 1;
            }
            c = j+1; // <-- big performance boost if duplicate characters
            let (ii, sz) = expand(i, j, b);
            if sz > bst {
                bst = sz;
                start = ii;
            }
        }
        let mut res = String::from("");
        for i in start..(start + bst) {
            res.push(b[i] as char);
        }
        return res;
    }
}