Longest Common Prefix

Find the longest common prefix string shared among an array of strings.

TimeO(n·m log n)

SpaceO(n·m)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string.

Constraints

Input: one line of space-separated strings (read from stdin with split()).
Output: print the longest common prefix on one line (once per approach in the reference solution).
Empty prefix: print a blank line when the answer is "".
Single string: the string itself is the answer.

Input

flower flow flight

Output

fl

Explanation: All three strings share the prefix 'fl'.

Naive Solution

Vertical scanning: start with prefix = strings[0]. For each remaining string, shrink prefix from the right (drop the last character) until string.startswith(prefix).

If prefix becomes empty, return "" immediately.

// Start with strings[0] as prefix; shrink from the end until all strings match.
// Time: O(n·m)  Space: O(1)
fn longest_common_prefix_naive(strings: &[String]) -> String {
    if strings.is_empty() {
        return String::new();
    }
    if strings.len() == 1 {
        return strings[0].clone();
    }
 
    let mut common_prefix = strings[0].clone();
    for string in strings.iter().skip(1) {
        while !string.starts_with(&common_prefix) {
            common_prefix.pop();
            if common_prefix.is_empty() {
                return String::new();
            }
        }
    }
    common_prefix
}

Time — O(n·m)

n strings, each comparison/shrink pass touches up to m characters of the current prefix.

Space — O(1)

Only the running prefix string — no extra collection beyond that.

Time: shrinking one character at a time can revisit the same prefix many times across strings.

Space: O(1) extra, but repeated startswith checks add overhead.

Next step: sort the strings lexicographically — the global LCP is exactly the LCP of the first and last sorted strings.

Optimal Solution

Sort the array lexicographically, then compare sorted[0] and sorted[-1] left to right:

While first[i] == last[i], append first[i] to the answer.
Stop on the first mismatch or when either string ends.

After sorting, every string lies between the endpoints — so the shared prefix cannot extend beyond their common prefix.

Guard: empty input → ""; single string → return it.

// Sort lexicographically; LCP of all strings equals LCP of sorted endpoints.
// Time: O(n·m log n)  Space: O(n·m)
fn longest_common_optimal(strings: &[String]) -> String {
    if strings.is_empty() {
        return String::new();
    }
    if strings.len() == 1 {
        return strings[0].clone();
    }
 
    let mut sorted_strings: Vec<String> = strings.to_vec();
    sorted_strings.sort();
 
    let first = sorted_strings[0].as_str();
    let last = sorted_strings.last().unwrap().as_str();
    let first_chars: Vec<char> = first.chars().collect();
    let last_chars: Vec<char> = last.chars().collect();
    let mut common_prefix = String::new();
 
    for idx in 0..first_chars.len() {
        if idx < last_chars.len() && first_chars[idx] == last_chars[idx] {
            common_prefix.push(first_chars[idx]);
        } else {
            break;
        }
    }
    common_prefix
}

Time — O(n·m log n)

Sorting n strings with O(m) comparisons each dominates; the endpoint scan is O(m).

Space — O(n·m)

sorted() / to_vec() allocates a copy of the string data.

Result: same answer as vertical scanning, with only two strings compared after sort instead of shrinking against every string.

Full source: Rust · Python