Longest Common Prefix
Last Updated: March 20, 2026
Understanding the Problem
A prefix of a string is any leading substring. For example, the prefixes of "flower" are "", "f", "fl", "flo", "flow", "flowe", and "flower". The longest common prefix (LCP) is the longest string that is a prefix of every string in the array.
One important detail: any string in the array could be empty, and an empty string has no characters to share. So if even one string is "", the answer is immediately "". Similarly, the LCP can never be longer than the shortest string in the array, because a prefix of a shorter string can't be longer than the string itself.
The core challenge is figuring out an efficient way to compare characters across all strings simultaneously.
Key Constraints:
1 <= strs.length <= 200→ The array has at most 200 strings. Even O(n^2) approaches on the number of strings are fine.0 <= strs[i].length <= 200→ Each string is at most 200 characters. A string can be empty.- Only lowercase English letters → No need to handle unicode or special characters.
Approach 1: Vertical Scanning
Intuition
The most natural way to find a common prefix is to check character by character. Look at position 0 of every string. Are they all the same? If yes, move to position 1. Keep going until you find a position where the characters differ, or you run out of characters in some string.
Think of the strings stacked on top of each other like rows in a grid. You're scanning down each column. The moment a column isn't uniform, you stop.
Algorithm
- If the array is empty, return
"" - For each character position
istarting from 0: - Get the character at position
ifrom the first string - For every other string in the array:
- If
iequals the length of that string (we've run past it), return the prefix so far - If the character at position
idoesn't match, return the prefix so far - If we get through all characters of the first string without stopping, the entire first string is the common prefix
Example Walkthrough
Code
- Time Complexity: O(S) where S is the sum of all characters in all strings. In the worst case (all strings are identical), we visit every character in every string exactly once. In the best case (first character differs), we check just one character per string.
- Space Complexity: O(1). We only use a few variables. The returned string doesn't count toward extra space.
The vertical scanning approach is already optimal in the worst case since we have to look at every character at least once. But there are other interesting strategies. The sorting approach, for instance, avoids comparing all strings against each other by leveraging a neat property of lexicographic order.
Approach 2: Sorting
Intuition
Here's a clever observation: if you sort the array of strings lexicographically, the first and last strings in the sorted order are the most different from each other. Any prefix that's common to both of these "extreme" strings must also be common to every string in between.
Why? Because sorting arranges strings by their characters from left to right. If the first sorted string starts with "fl" and the last sorted string also starts with "fl", then every string between them must also start with "fl". So instead of checking all n strings, we just sort and compare two.
Algorithm
- If the array is empty, return
"" - Sort the array of strings lexicographically
- Compare the first and last strings character by character
- The common prefix of these two strings is the answer
Example Walkthrough
Code
- Time Complexity: O(n m log n) where n is the number of strings and m is the average string length. Sorting n strings takes O(n * log n) comparisons, and each comparison takes O(m) time since we're comparing strings character by character. After sorting, we do one O(m) scan to find the prefix.
- Space Complexity: O(m) for the space used by the sorting algorithm. Most sorting algorithms need O(log n) stack space, but string comparisons involve O(m) length strings.
The sorting approach trades optimal time complexity for elegance. Divide and conquer offers yet another structural perspective, splitting the problem into halves and combining results.
Approach 3: Divide and Conquer
Intuition
Divide and conquer gives us a different angle on this problem. The key observation is: the longest common prefix of an array of strings is the same as the longest common prefix of (the LCP of the left half) and (the LCP of the right half).
In other words, LCP(S1, S2, ..., Sn) = LCP(LCP(S1, ..., Smid), LCP(Smid+1, ..., Sn)).
We keep splitting until we reach individual strings (which are their own LCP), then merge results back up by finding the common prefix of two strings at each level. This is the same pattern as merge sort: split the problem, solve each half, combine the results.
Algorithm
- If the array is empty, return
"" - Call a recursive function
findLCP(strs, left, right): - Base case: If
left == right, returnstrs[left](a single string is its own prefix) - Divide: Find
mid = (left + right) / 2 - Conquer: Recursively find
lcpLeft = findLCP(strs, left, mid)andlcpRight = findLCP(strs, mid + 1, right) - Combine: Return the common prefix of
lcpLeftandlcpRight
Example Walkthrough
Code
- Time Complexity: O(S) where S is the sum of all characters in all strings. There are O(log n) levels of recursion, and at each level, we do O(S) total character comparisons. In practice, early termination from short common prefixes makes this faster.
- Space Complexity: O(m * log n) where m is the length of the longest common prefix. The recursion depth is O(log n), and at each level we store intermediate LCP strings of length up to m.