LESSON 185 OF 414 · LOOPS - CHALLENGES

Longest Common Prefix of Two Strings in Rust: One Pass over Characters

Given two strings s1 and s2, return their longest common prefix

Example 1:

Input:  s1 = "hello", s2 = "help"
Output:  "hel"

Example 2:

Input:  s1 = "Andy", s2 = "Mircea"
Output:  ""

Example 3:

Input:  s1 = "AlgoCademy", s2 = "Algo"
Output:  "Algo"

STEP 1 OF 6

Guided

Ctrl + Enter to check

RUST · LOOPS - CHALLENGES

Longest Common Prefix Of Two Strings in Rust, explained

Problem overview

The function longest_common_prefix takes two strings, s1 and s2, and returns the longest string that both of them start with. For "hello" and "help" the answer is "hel": the first three characters match, and then l meets p. For "Andy" and "Mircea" the first characters already differ, so the answer is the empty string. For "AlgoCademy" and "Algo" the answer is "Algo", because the shorter string is itself a prefix of the longer one.

Approach

Compare the strings position by position from the start. While the characters at the same position are equal, they belong to the prefix, so we add them to the result. The first mismatch ends the prefix, since a common prefix must be unbroken from the start. Later positions might match again, for example in "abxd" and "abyd" the last characters are equal, but they are not part of a prefix.

There is also a limit on how far to look: the prefix cannot be longer than the shorter string. Comparing only up to the shorter length means every index is valid in both strings.

The brute-force alternative, trying every prefix length and checking it with starts_with, repeats comparisons. The single pass compares each position at most once.

Step by step

Collect the characters of both strings into vectors. Rust does not let you write s1[i] on a String. Text is stored as UTF-8 bytes, and a character can use more than one byte, so a position in the text is ambiguous. Collecting chars() into a Vec<char> gives plain indexing by character.
Prepare the result and the limit. result starts as an empty String and must be mut. min_len is the smaller of the two lengths, computed with min.
Loop over the indices 0..min_len. The range excludes min_len, so each index exists in both vectors.
Compare the characters. If chars1[i] equals chars2[i], append that character to result with push, which adds one char.
Stop at the first difference. In the else branch, break leaves the loop.
Return result. That line runs after a break and also when the loop finishes all min_len positions, which is the case when the shorter string is a prefix of the other.

The solution in Rust

impl Solution {
    fn longest_common_prefix(s1: String, s2: String) -> String {
        let chars1: Vec<char> = s1.chars().collect();
        let chars2: Vec<char> = s2.chars().collect();
        let mut result = String::new();
        let min_len = chars1.len().min(chars2.len());
        for i in 0..min_len {
            if chars1[i] == chars2[i] {
                result.push(chars1[i]);
            } else {
                break;
            }
        }
        return result;
    }
}

Language details:

String versus &str. The parameters are owned String values, so the function takes ownership of its arguments. We only read from them, which is why we can call chars() on them directly.
Type annotations on collect. collect() can build many collections, so the compiler needs to know which one. The annotation Vec<char> on the variable tells it.
char is a Unicode scalar value, 4 bytes wide, not a byte. The vector holds one entry per character, so chars1.len() counts characters, while s1.len() would count bytes. For "héllo" and "hélp", the function returns "hél", three characters. A byte-based comparison would work differently, because é takes two bytes.
min on integers. chars1.len().min(chars2.len()) returns the smaller usize. The indices are usize too, which is what indexing requires.
return result; is legal at the end of a function, though idiomatic Rust often leaves out return and the semicolon and ends with the bare expression result.
push versus push_str. push appends one char, and push_str appends a string slice.

Tracing an example

With s1 = "hello" and s2 = "help", chars1 has 5 entries and chars2 has 4, so min_len is 4. At i = 0 both characters are h, so result becomes "h". Then e matches e and l matches l, which gives "hel". At i = 3 the characters are l and p, which differ, so the loop breaks and the function returns "hel". The final o of "hello" is never looked at.

Complexity

Collecting the characters takes O(n + m) time for strings of lengths n and m. The loop does at most min(n, m) iterations with constant work each. The total time is O(n + m). The two vectors and the result take O(n + m) extra space. This could be reduced to O(1) beyond the result by walking both chars() iterators together with zip, but the vectors keep the lesson's code simple and indexable.

Edge cases and common mistakes

An empty string. min_len is 0, the loop body never runs, and the result is the empty string.
No common prefix. The first comparison fails and break leaves result empty.
Identical strings. The loop matches every position, and the result equals the string.
One string is a prefix of the other. The loop finishes without a break, and the shorter string comes back whole.
Looping to the longer length. Indexing past the end of the shorter vector panics, because out-of-bounds indexing is checked in Rust. Always bound the loop by min_len.
Forgetting break. Without it, matching characters after a mismatch would be added to the result, and "abxd" with "abyd" would give "abd" instead of "ab".
Case. The comparison is case-sensitive, so "Algo" and "algo" have an empty common prefix.

Testing

"hello", "help" gives "hel".
"Andy", "Mircea" gives "".
"AlgoCademy", "Algo" gives "Algo".
"", "x" gives "".

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free