Problem editorial

Longest Common Prefix

EasyString Manipulation PatternsArrayStringString Matching

Longest Common Prefix: the approach in brief

The problem

Given strs, a list of strings, find the longest common prefix shared by every string in the list. A prefix is a contiguous sequence of characters beginning at index 0 of a string; the empty string is also a valid prefix.

Pattern

Longest Common Prefix is a String Manipulation Patterns problem, in the Naive / KMP / Rabin-Karp subpattern. The pattern covers palindrome checking, anagram detection, pattern matching, and string conversion

Approach outline

The answer cannot be longer than the shortest string.
Use one string as a candidate prefix and compare it with the others.
Scan candidate characters from left to right, stopping at the first mismatch or when a string ends.

Complexity

The reference solution runs in O(n * m), where n is the number of strings and m is the length of the shortest string. time and O(1) auxiliary space, excluding the returned prefix. space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Longest Common Prefix and the problems around it

Longest Common Prefix is a String Manipulation Patterns problem, in the Naive / KMP / Rabin-Karp subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Longest Common Prefix