Find the longest palindromic subsequence - Using a hashmap in Rust

Question

This is a leetcode question which I wanted to solve using Rust as I'm learning Rust at the moment. I would appreciate some feedback on how to write it idiomatically.

Link to the question: https://leetcode.com/problems/longest-palindromic-subsequence/

Things that I'm particularly unsure about:

• Should I be using String or &str?
• Am I using the hashmap correctly? In particular, am I handling the Option output from the get method in an idiomatic way?

My solution:

use std::cmp::max;
use std::collections::HashMap;

pub fn  longest_palindrome_subseq(s: String) -> i32 {
    fn solve(s: String, cache: &mut HashMap<String, i32> ) -> i32 {
        if cache.contains_key(&s) {
            return *cache.get(&s).unwrap();
        }

        let length = s.len();
        if length == 0 {
            return 0;
        }
        if length == 1 {
            return 1;
        }

        let first_letter = &s[..1];
        let last_letter = &s[length-1..];
        let solution: i32;
        if first_letter == last_letter {
            solution = 2 + solve(s[1..s.len()-1].to_string(), cache);
        } else {
            solution =  max(
                solve(s[1..s.len()].to_string(), cache),
                solve(s[..s.len()-1].to_string(), cache),
            );
        }
        cache.insert(s, solution);
        solution
    }

    let mut cache: HashMap<String, i32> = HashMap::new();
    solve(s, &mut cache)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty() {
        let actual = longest_palindrome_subseq("".to_string());

        assert_eq!(actual, 0);
    }

    #[test]
    fn test_single() {
        let actual = longest_palindrome_subseq("a".to_string());

        assert_eq!(actual, 1);
    }

    #[test]
    fn test_double_not_same() {
        let actual = longest_palindrome_subseq("ab".to_string());

        assert_eq!(actual, 1);
    }

    #[test]
    fn test_double_same() {
        let actual = longest_palindrome_subseq("aa".to_string());

        assert_eq!(actual, 2);
    }

    #[test]
    fn test_triple() {
        let actual = longest_palindrome_subseq("aba".to_string());

        assert_eq!(actual, 3);
    }

    #[test]
    fn test_1() {
        let actual = longest_palindrome_subseq("bbbab".to_string());

        assert_eq!(actual, 4);
    }

    #[test]
    fn test_2() {
        let actual = longest_palindrome_subseq("cbbd".to_string());

        assert_eq!(actual, 2);
    }
}

Answer 1

Good questions!

Yes, You Should be Using &str

In this algorithm, all of your hash-map keys are substrings of the same input string, which will outlive the hash map. It is much more efficient to copy and work with slices of the input string than it is to allocate new String objects and make a deep copy of each substring.

Doing it this way means you will need to create two lifetimes: one for the HashMap and a longer one for the substring slices, including the keys of the HashMap, which may not outlive its keys. The substrings similarly may not outlive the string they index. It’s common practice to give these lifetimes names like 'a and 'b, but you could name them anything, such as:

fn solve<'substrings, 'map>(
    s: &'substrings str,
    cache: &'map mut HashMap<&'substrings str, i32>,
) -> i32

You could also make the constraint that the map keys outlive the map that contains them explicit, although this is not necessary for the code to compile:

fn solve<'map, 'substrings: 'map>(
    s: &'substrings str,
    cache: &'map mut HashMap<&'substrings str, i32>,
) -> i32

This is initially called as solve(s, &mut cache) from longest_palindrome_subseq(s: &str). The local variable cache expires when the function returns, and it’s declared to have a type of Hashmap<&str, i32>, so the lifetime 'substrings is inferred to be the lifetime of its keys, which is at least as long as the lifetime of cache and no longer than the lifetime of s, and everything works. (If the compiler were not able to infer all this, you could also give the lifetime of the input slice a name, e.g. s: &'input str, and explicitly declare the lifetime of the keys as cache: HashMap<&'input str, i32>. Again, that complexity is not necessary here.)

This necessitates a few syntactic changes to the body and tests (see below) to match the new type, such as removing every call to .to_string(). That’s a concrete sign of the improved efficiency: you’re removing expensive operations and replacing them with cheap, constant-time ones.

Prefer Pattern Matching on the Output

Again, great question, and exactly what I would have addressed.

Rather than make two calls to the HashMap, and using an unwrap that theoretically shouldn’t fail, you would be better off using a pattern guard, such as:

if let Some(&result) = cache.get(s) {
    return result;
}

This is not only more succinct, it eliminates all the branches of control flow that would be logic errors (but which the compiler, or a maintainer, cannot prove are impossible).

I would similarly suggest making solution a static single assignment, rather than declaring it uninitialized and then trying to make sure it is assigned exactly once in every possible branch before being used. Initializing it to an if or match expression makes several tricky types of bug impossible to write (although at least the compiler should be able to catch them).

You could also combine the tests for a usize value of 0 or 1 into a single comparison.

In the Real World, Remember that Not All Strings are ASCII

Part of the LeetCode problem statement is that the string contains only “English letters,” encoded as a single byte in UTF-8. (In the future, please copy all relevant requirements into the post, rather than giving an external link that could change or go dead.)

If, however, you ever passed this function a string containing a non-ASCII character, the recursive calls would create a substring that did not start and end on a valid UTF-8 boundary. That would crash the program at runtime. If you don’t want that to happen, you might want to test the input for validity, to return an error Result or fail fast and gracefully.

if s.bytes().any(|b| {b > 127}) {
    unimplemented!("Input must be ASCII!");
}

A fix might be to replace every expression that indexes a substring by bytes with one that iterates over its chars. For example. s.len() would become s.chars().count(), and returning a substring with the first or last char removed might use str::split and str::rsplit, respectively. In fact, even this might not be correct in the general case: you might want to check graphemes instead of Unicode codepoints for canonical equivalence. This, however, goes beyond what is provided in the Rust standard library.

Putting it all Together

Compare this version and see if it works for you:

use std::cmp::max;
use std::collections::HashMap;

pub fn  longest_palindrome_subseq(s: &str) -> i32 {
    fn solve<'map, 'substrings: 'map>(
        s: &'substrings str,
        cache: &'map mut HashMap<&'substrings str, i32>,
    ) -> i32 {
        if let Some(&result) = cache.get(s) {
            return result;
        }

        let length = s.len();
        if length < 2 {
            return length as i32;
        }

        // We have already checked that the length is greater than 1.
        let first_letter = s.chars().next().unwrap();
        let last_letter = s.chars().rev().next().unwrap();
        let solution = 
            if first_letter == last_letter {
                2 + solve(&s[1..s.len()-1], cache)
            } else {
                max(
                    solve(&s[1..s.len()], cache),
                    solve(&s[..s.len()-1], cache)
                )
            };
        cache.insert(s, solution);
        solution
    }

    if s.bytes().any(|b| {b > 127}) {
        unimplemented!("Input must be ASCII!");
    }
    let mut cache: HashMap<&str, i32> = HashMap::new();
    solve(s, &mut cache)
}


pub fn main() {
    assert_eq!(longest_palindrome_subseq(""), 0);
    assert_eq!(longest_palindrome_subseq("a"), 1);
    assert_eq!(longest_palindrome_subseq("ab"), 1);
    assert_eq!(longest_palindrome_subseq("aa"), 2);
    assert_eq!(longest_palindrome_subseq("aba"), 3);
    assert_eq!(longest_palindrome_subseq("bbbab"), 4);
    assert_eq!(longest_palindrome_subseq("cbbd"), 2);
}