</>EmbeddedInterview

How do you find the longest common prefix of a set of strings?

EasyArrays & Strings (Coding Round)

Short answer: Compare the strings column by column: take character i of the first string and check that every other string has the same character at i. Stop at the first mismatch or at the end of any string; the prefix is the first i characters. O(total characters) time, O(1) extra space.

#include <stddef.h>

/* returns the length of the common prefix; strs[0..n-1] are C strings, n >= 1 */
size_t common_prefix_len(const char *const *strs, size_t n)
{
    size_t i = 0;
    for (;; i++) {
        char c = strs[0][i];
        if (c == '\0') return i;
        for (size_t k = 1; k < n; k++)
            if (strs[k][i] != c)          /* also stops at a shorter string's '\0' */
                return i;
    }
}
/* {"flower", "flow", "flight"} -> 2 ("fl") */

Why the '\0' check works for shorter strings: if another string ends at position i, its character there is '\0', which differs from c (non-zero), so the loop stops without reading past its end.

Alternatives: horizontal scanning (prefix of the first two, then shrink against each next string), sorting and comparing only the first and last strings (they differ the most), or divide and conquer. All are O(total characters); the vertical scan stops earliest.

Embedded relevance: matching command prefixes in a CLI parser (e.g. accept "sta" for "status" if unique), or grouping file paths/topics by common prefix in an MQTT broker.