Two inputs, one output lifetime

When a function takes two references and returns one, Rust's lifetime elision rules cannot guess which input the result borrows from, so you must write the lifetimes yourself. This problem is about choosing them precisely: the returned reference should be tied only to the input it actually points into.

Implement two functions:

pub fn first_match<'a>(haystack: &'a [String], pattern: &str) -> Option<&'a str>
pub fn longest_common_prefix<'a>(a: &'a str, b: &str) -> &'a str

The contract

first_match scans haystack in order and returns the first element that contains pattern as a substring, or None if no element does. Matching is exact and case-sensitive ("Apple" does not contain "a"), with no Unicode normalization. An empty pattern is contained in every string, including the empty string, so it matches the first element; an empty haystack always gives None.

longest_common_prefix returns the longest prefix shared by a and b, returned as a slice of a. Strings are compared one char (Unicode scalar value) at a time, again with no normalization: a precomposed "é" (U+00E9) and "e" followed by a combining accent (U+0065 U+0301) differ at their first char, so their common prefix is "". If either string is empty, or the first chars differ, the result is "". If one string is a prefix of the other, the result is the whole shorter string.

The test driver prints the two results as a JSON object, using null when first_match returns None. For example, with haystack ["apple", "banana", "cherry"], pattern "an", a = "hello" and b = "help", the output is {"first_match":"banana","lcp":"hel"}.

Why the lifetimes matter

If you leave both lifetimes out, each function fails to compile with E0106: missing lifetime specifier. Elision gives every reference parameter its own lifetime, and with two of them (and no self) there is no rule that says which one the output should use.

One fix that compiles is to give everything the same lifetime:

pub fn first_match<'a>(haystack: &'a [String], pattern: &'a str) -> Option<&'a str>

This signature promises less than the function can deliver. It says the result may only be used while both haystack and pattern are still borrowed. But the result points into haystack; pattern is only read during the search. A caller that holds the result therefore has to keep the pattern alive too, even though nothing needs it.

The test driver for this problem does exactly what such a caller might do. It builds the pattern (and b) in an inner block, calls your functions, and uses the results after that block has ended:

let found: Option<&str>;
{
    let pattern = input.get("pattern").as_str().to_string();
    found = first_match(&haystack, &pattern);
} // `pattern` is dropped here
// `found` is used here; it borrows from `haystack`, which is still alive.

With the correct signature this compiles. With the single-lifetime signature it fails with E0597: pattern does not live long enough, because the signature says found might borrow from pattern.

The rule to apply: give the output's lifetime only to the parameters the output can borrow from. Every other reference parameter can keep an elided lifetime, which means you write a plain &str and never name it.

The signature pins

The starter code ends with two lines that you must not edit or delete:

const _: for<'a, 'b> fn(&'a [String], &'b str) -> Option<&'a str> = first_match;
const _: for<'a, 'b> fn(&'a str, &'b str) -> &'a str = longest_common_prefix;

Each line converts your function to a function-pointer type. for<'a, 'b> means the pointer must work for any two lifetimes, including two that are unrelated. A function that requires both inputs to share one lifetime cannot meet that, so the conversion fails with E0308: mismatched types ("one type is more general than the other"). A pin with one lifetime, for<'a> fn(&'a [String], &'a str) -> Option<&'a str>, would accept both the correct and the over-constrained signature, which is why these pins use two. The pins also reject a different return type, such as an owned String.

Lifetimes do not exist when the program runs, so comparing outputs cannot detect a signature that is too strict. The pins and the driver's inner block check it at compile time instead. The starter code deliberately uses the single-lifetime signatures, so it does not compile until you fix them.

The multibyte trap in longest_common_prefix

A natural first attempt compares bytes:

let n = a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count();
&a[..n]   // can panic

Try a = "héllo", b = "hèllo". In UTF-8, é is the two bytes 0xC3 0xA9 and è is 0xC3 0xA8. The first two bytes of the strings (h and 0xC3) are equal, so n == 2, which is in the middle of é. Slicing a str at a byte offset that is not on a character boundary panics at run time; it is not a compile error. One of the hidden tests uses exactly this input. Iterating over chars avoids the problem: char_indices yields the byte offset where each char starts, and every such offset is a valid place to slice.

Also handle the case where the loop finds no differing char, because one string ran out. The answer is then the whole shorter string, which ends in a at byte offset a.len().min(b.len()). Use byte lengths here, not char counts, because slicing a str takes byte offsets.