How do you approach Longest Common Prefix?

Compare characters at the same position across all strings.

What is the time complexity of Longest Common Prefix?

Time complexity: O(S) where S is the sum of all characters. Space complexity: O(1).

What are common mistakes on Longest Common Prefix?

Building the result with repeated concatenation in a loop - quadratic in most languages; collect into a list and join, or use a string builder. Assuming one character is one code unit. Non-ASCII input breaks index arithmetic. Comparing strings or boxed characters by reference rather than by value.

gitGood.dev

← Back to problems

Longest Common Prefix

EasyAlgorithms

Description

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 "".

Example 1

Input: strs = ["flower","flow","flight"]

Output: "fl"

Example 2

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation: There is no common prefix among the input strings.

Constraints

- 1 <= strs.length <= 200 - 0 <= strs[i].length <= 200 - strs[i] consists of only lowercase English letters.

Longest Common Prefix: approach, complexity and pitfalls

An easy strings problem, graded against 6 test cases (3 of them hidden).

The pattern: Strings

Parsing, comparison, and character-frequency reasoning.

Reach for it when you see: String input where the work is scanning, comparing, or counting characters.

If you are stuck

Show the 3-step hint ladder

Compare characters at the same position across all strings.
Stop when you find a mismatch or reach the end of any string.
You can use the first string as a reference.

The optimal approach

Show the approach: Vertical Scanning

Compare characters column by column across all strings. Stop when a mismatch is found or we reach the end of any string.

Time: O(S) where S is the sum of all characters
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Strings mistakes

These apply to the pattern as a whole, not just this problem.

Building the result with repeated concatenation in a loop - quadratic in most languages; collect into a list and join, or use a string builder.
Assuming one character is one code unit. Non-ASCII input breaks index arithmetic.
Comparing strings or boxed characters by reference rather than by value.