Longest Common Prefix
EasyPrompt
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 <= 2000 <= strs[i].length <= 200strs[i]consists of only lowercase English letters if it is non-empty.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach reframes the problem as a search problem. We know the length of the longest common prefix must be between 0 and the length of the shortest string in the array. This bounded range allows us to use binary search to efficiently find the optimal length.
Algorithm
- Find
minLen, the length of the shortest string in the array. The LCP cannot be longer than this. - Initialize a search range for the length,
low = 0,high = minLen. - While
low <= high:- Calculate the middle length
mid = low + (high - low) / 2. - Check if a common prefix of length
midexists across all strings. To do this, take the prefix of the first string,strs[0].substring(0, mid), and verify if all other strings start with it. - If a common prefix of length
midexists, it means we might find an even longer one. We recordmidas a potential answer and search in the right half:low = mid + 1. - If it does not exist,
midis too long. We must search for a shorter prefix in the left half:high = mid - 1.
- Calculate the middle length
- After the loop terminates, the last successfully recorded length corresponds to the longest common prefix. Return
strs[0].substring(0, lastSuccessfulLength).
Walkthrough
The core idea is to binary search for the length of the longest common prefix. We first determine the maximum possible length by finding the length of the shortest string in the array, let's call it minLen. Our search space for the length is then [0, minLen]. For each length k we test (picked by the binary search), we check if the first k characters are a common prefix for all strings in the array. If they are, we know the LCP is at least k characters long, so we try a larger length. If they are not, k is too large, and we must try a smaller length. We continue this process until the search space is exhausted, and the largest k that worked is our answer.
class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } int minLen = Integer.MAX_VALUE; for (String str : strs) { minLen = Math.min(minLen, str.length()); } int low = 0; int high = minLen; while (low <= high) { int middle = low + (high - low) / 2; if (isCommonPrefix(strs, middle)) { low = middle + 1; } else { high = middle - 1; } } return strs[0].substring(0, (low + high) / 2); } private boolean isCommonPrefix(String[] strs, int len) { if (len == 0) return true; String prefix = strs[0].substring(0, len); for (int i = 1; i < strs.length; i++) { if (!strs[i].startsWith(prefix)) { return false; } } return true; }}Complexity
Time
O(N * M * log M)
Space
O(M)
Trade-offs
Pros
An interesting application of the binary search algorithm to a string problem.
Cons
Significantly less efficient in terms of time complexity compared to other approaches.
The logic is more complex to implement correctly than simple scanning methods.
Solutions
Solution
public class Solution { public string LongestCommonPrefix ( string [] strs ) { int n = strs . Length ; for ( int i = 0 ; i < strs [ 0 ]. Length ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { if ( i >= strs [ j ]. Length || strs [ j ][ i ] != strs [ 0 ][ i ]) { return strs [ 0 ]. Substring ( 0 , i ); } } } return strs [ 0 ]; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.