3043. Find the Length of the Longest Common Prefix - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given an array of strings, find the longest common prefix among them. If no common prefix exists, return an empty string "".

Constraints:

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

Examples

Example 1

Input:

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

Output:

"fl"

Explanation:

"fl" is the longest common prefix of all the given words.

Example 2

Input:

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

Output:

""

Explanation:

There is no common prefix among these words, so the result is an empty string.

Hints:

A common prefix means the prefix must be present in all strings.
The shortest string in the list determines the maximum possible prefix length.
A binary search or divide and conquer strategy can be used to optimize the search for the prefix.

Approach 1: Brute Force (Horizontal Scanning)

Idea

Assume the first string is the initial common prefix.
Compare this prefix with each of the other strings one by one.
If a mismatch is found at some position, truncate the prefix up to the character before the mismatch.
Continue until the prefix has been checked against all strings or becomes empty.

This approach is also known as horizontal scanning because we take one string and compare horizontally across the others.

Algorithm

If the input list is empty, return "" (but given the constraints, this case won't occur).
Initialize the prefix as the first string in the list.
Loop through each of the remaining strings:
- While the current string does not start with the prefix (i.e., prefix is not a prefix of the string), shorten the prefix by removing its last character.
- If at any point the prefix becomes empty, return "" immediately (no common prefix).
After checking all strings, whatever remains in prefix is the longest common prefix.

Time Complexity

O(N × M) in the worst case, where N is the number of strings and M is the length of the shortest string.
- In the worst scenario, we might compare each character of the shortest string with all other strings.
- Each comparison of startswith or character check is O(1), done up to M characters for each of N-1 comparisons.
Space Complexity: O(1) extra space (we use only a few variables; prefix manipulation is in-place on the first string).

Python Implementation:

Python3

. . . .

Java Implementation:

Java

. . . .

Explanation: In this brute-force solution, we progressively narrow down the candidate prefix. We start with the entire first string and then chop it down until it fits as a prefix of the second string. Then we ensure that resulting prefix fits the third string, and so on. This guarantees the prefix at the end is as long as possible while still being common to all strings.

Approach 2: Divide and Conquer

Idea

Use a divide-and-conquer strategy to split the problem into subproblems:

If we split the list of strings into two halves, the longest common prefix of the whole list must be a prefix of the longest common prefix of each half.
Recursively find the longest common prefix for the left half and the right half of the list.
Then find the common prefix of those two results, which will be the answer for the full list.

This approach effectively reduces the comparison domain by combining results from sub-solutions.

Algorithm

If there is only one string in the range [left, right], return that string (the base case of recursion).
Otherwise, divide the range [left, right] into two halves:
- Compute mid = (left + right) // 2.
- Recursively find the longest common prefix for the left half ([left, mid]).
- Recursively find the longest common prefix for the right half ([mid+1, right]).
Once you have the longest prefix for the left part and the right part, compare these two prefix strings character by character to determine their common prefix.
Return this common prefix of the two halves.

Time Complexity

O(N × M) in the worst case. In the worst scenario (e.g., all strings are identical), the divide and conquer approach still has to compare a total of N * M characters.
However, on average, it may perform fewer comparisons than the brute force approach because it often can discard half of the array at each recursion level and combine results with shorter prefixes. The recursion depth is O(log N), and at each level we do comparisons up to M characters for merging, resulting in a complexity closer to O(N * M * log N) in some analyses. But asymptotically for worst-case, it's not better than the brute force scan.
Space Complexity: O(M * log N) in the worst case for recursion stack and storing intermediate prefixes. Each recursion level might store a prefix up to length M, and there are log N levels. (If we don't count the output result itself, extra space is mostly for recursion.)

Python Implementation:

Python3

. . . .

Java Implementation:

Java

. . . .

Explanation: We recursively split the array of strings until we reach single-string subproblems, which are trivially their own prefix. Then we unwind the recursion, at each step calculating the common prefix of two results. For example, if we split ["flower","flow","flight"] into ["flower","flow"] and ["flight"], we get the longest prefix of the first part as "flow" and of the second part as "flight" (trivial, since there's only one string). Then we find the common prefix of "flow" and "flight", which is "fl".

Other Approaches and Optimizations

Binary Search on Prefix Length:
Instead of checking character by character, we can use a binary search on the length of the prefix:
1. Find the minimum length minLen among all strings (maximum possible common prefix length).
2. Use binary search between 1 and minLen. For a given mid-length L, check if all strings share the same prefix of length L.
3. If they do, it means a prefix of length L is common, so move the binary search right (try a longer prefix).
4. If they don't, move the binary search left (try a shorter prefix).
5. Continue until the range narrows. The longest length that worked is the length of the longest common prefix.
Complexity: Checking a prefix of length L across N strings takes O(N * L) time. We do this O(log M) times (where M = minLen) due to binary search. Hence the complexity is roughly O(N * M * log M). Space complexity is O(1). In practice, this is efficient when strings are long because it reduces the number of comparisons by skipping lengths that are not possible.
Using Sorting:
A clever trick is to sort the array of strings (which is O(N * M * log N) due to string comparisons). After sorting, the common prefix of the entire array must be a prefix of the first and last strings (the smallest and largest in lexicographical order). So, you only need to compare the first and last string character by character until they differ. This yields the longest common prefix. While the sorting step can be more expensive than other methods for large N, it can be convenient to implement and still ensures an O(N * M * log N) upper bound.
Trie (Prefix Tree) Approach:
You can build a Trie of all the strings, where each node represents a character and has children for subsequent characters. After inserting all strings into the Trie, you traverse from the root downwards as long as the current node has exactly one child and is not marked as the end of a string. The characters you accumulate along this path form the longest common prefix. This approach has a time complexity of O(N * M) to build the Trie and O(M) to find the prefix, and a space complexity of O(N * M) in the worst case (if no two strings share any prefix, the Trie contains all characters of all strings). Although a Trie might be overkill for this specific problem, it's a useful data structure for many prefix-related problems (like auto-complete systems, prefix-based searches, etc.).

Complexity Analysis and Comparison

To summarize the approaches, here is a comparison of their time and space complexities:

Approach	Time Complexity	Space Complexity	Description
Horizontal Scanning (Brute Force)	O(N * M)	O(1)	Compare characters of a running prefix with each string; shorten on mismatch. Simple to implement.
Divide and Conquer	O(N * M) worst-case<br>(~O(N M * log N) average)*	O(M * log N) (due to recursion)	Recursively find LCP of halves and merge. Can be more efficient in practice if it eliminates large parts early.
Binary Search on Length	O(N * M * log M)	O(1)	Binary search the prefix length. Fewer character comparisons for long strings, but requires careful implementation of length checks.
Sorting Method	O(N * M * log N)	O(1) or O(N) extra	Sort strings then compare only the first and last string. Sorting dominates time for large N.
Trie (Prefix Tree)	O(N * M)	O(N * M)	Build a trie of all strings and traverse it until a split. Useful if you need to reuse the trie for multiple queries, otherwise uses a lot of memory.

N is the number of strings, and M is the length of the shortest string (which limits the common prefix length).

Note: In the worst case (e.g., all strings are identical), any algorithm will have to inspect at least N * M characters, because you must verify each character of each string. Thus, O(N*M) is a lower bound for the problem. The differences in approaches come down to practical performance on average and ease of implementation.

Common Mistakes

Not handling differing lengths: Forgetting to stop when one string ends. For example, if one string is a prefix of another (like "ab" and "abc"), a loop that iterates character by character might run past the end of the shorter string. Always consider the minimum length or check boundaries to avoid index errors.
Early return vs. trimming logic: Some try to build the prefix character by character and return when a mismatch is found. It’s easy to make an off-by-one error in such logic. The horizontal scanning method that repeatedly uses startsWith or the vertical scanning method that checks each index across all strings can help avoid this.
Ignoring empty string cases: If any string in the array is empty (""), the longest common prefix must be "". Code should handle this scenario. The brute force approach inherently handles it (the first while check will immediately shorten prefix to empty), but if writing your own loop, ensure you return empty string if an empty string is present.
Modifying the first string directly: Some in-place attempts might try to shorten the first string itself as the prefix. This works if done carefully (as in our approach), but be cautious: if you accidentally modify or check beyond bounds, you could ruin the original data. Using a separate prefix variable (like we did) is safer.
Not considering one-string input: If the array has only one string, that string itself is the longest common prefix. Some solutions might incorrectly return "" if they always assume a comparison between multiple strings. Always handle the single-string case (our approaches naturally cover this by either returning early or just falling through to returning the first string).

Edge Cases

Single string in array: e.g., ["alone"] should return "alone" since there's nothing else to compare it to.
Array containing an empty string: e.g., ["", "hello", "hi"] should immediately return "" because an empty string has no prefix in common with non-empty strings.
All strings are identical: e.g., ["same", "same", "same"] should return "same". The algorithms should handle this by not cutting the prefix unnecessarily.
No common prefix at all: e.g., ["apple", "banana", "cherry"] should return "" as none of the strings share a starting letter. The first comparison itself will result in an empty prefix.
Mixed length strings with partial match: e.g., ["interstellar", "internet", "internal"]. Here the shortest string is "internal" (length 8), and the common prefix is "inte" (first 4 characters). The solution should correctly identify that and not be thrown off by longer strings in the array.
Very long common prefix: e.g., if you have many strings that are all the same for the first 100 characters, the algorithm needs to handle potentially large comparisons. All the approaches described will handle it within the given complexity bounds, but it's a reminder to ensure your implementation is efficient in scanning characters (using Python slicing or Java substring operations wisely, etc.).

3043. Find the Length of the Longest Common Prefix - Detailed Explanation

Problem Statement

Constraints:

Examples

Example 1

Input:

Output:

Explanation:

Example 2

Input:

Output:

Explanation:

Hints:

Approach 1: Brute Force (Horizontal Scanning)

Idea

Algorithm

Time Complexity

Python Implementation:

Java Implementation:

Approach 2: Divide and Conquer

Idea

Algorithm

Time Complexity

Python Implementation:

Java Implementation:

Other Approaches and Optimizations

Complexity Analysis and Comparison

Common Mistakes

Edge Cases

Related Problems