# Longest Common Prefix
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-common-prefix)
Canonical: https://scaleengineer.com/dsa/problems/longest-common-prefix
**Data structures:** String, Trie
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Airbus SE](https://scaleengineer.com/companies/airbus-se), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cognizant](https://scaleengineer.com/companies/cognizant), [Deloitte](https://scaleengineer.com/companies/deloitte), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Google](https://scaleengineer.com/companies/google), [HCL](https://scaleengineer.com/companies/hcl), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Pwc](https://scaleengineer.com/companies/pwc), [Roblox](https://scaleengineer.com/companies/roblox), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yelp](https://scaleengineer.com/companies/yelp), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [PornHub](https://scaleengineer.com/companies/pornhub), [Turing](https://scaleengineer.com/companies/turing), [CEDCOSS](https://scaleengineer.com/companies/cedcoss), [Disney](https://scaleengineer.com/companies/disney), [PhonePe](https://scaleengineer.com/companies/phonepe), [Roche](https://scaleengineer.com/companies/roche), [HSBC](https://scaleengineer.com/companies/hsbc), [CME Group](https://scaleengineer.com/companies/cme-group), [DXC Technology](https://scaleengineer.com/companies/dxc-technology), [Jane Street](https://scaleengineer.com/companies/jane-street), [Nokia](https://scaleengineer.com/companies/nokia), [PubMatic](https://scaleengineer.com/companies/pubmatic), [Revolut](https://scaleengineer.com/companies/revolut), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo)
---
## Problem
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 if it is non-empty.

# Approaches
## Binary Search on Length
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.
**Time:** O(N * M * log M) · **Space:** O(M)
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `mid` exists 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 `mid` exists, it means we might find an even longer one. We record `mid` as a potential answer and search in the right half: `low = mid + 1`.
  - If it does not exist, `mid` is too long. We must search for a shorter prefix in the left half: `high = mid - 1`.
- After the loop terminates, the last successfully recorded length corresponds to the longest common prefix. Return `strs[0].substring(0, lastSuccessfulLength)`.

## Divide and Conquer
This approach uses a divide and conquer strategy, a common paradigm in computer science. The problem of finding the LCP of an array of strings is broken down into smaller subproblems. We recursively find the LCP for the left and right halves of the array and then merge the results.
**Time:** O(S) · **Space:** O(M * log N)
**Pros:** An elegant, recursive solution that demonstrates the divide and conquer paradigm.; The work is well-distributed, which can be advantageous in parallel computing environments.
**Cons:** Higher space complexity due to the recursion call stack.; Can be slightly slower than iterative approaches due to the overhead of function calls.
### Explanation
The logic behind this method is that `LCP(S1, S2, ..., Sn) = LCP(LCP(S1, ..., Sk), LCP(Sk+1, ..., Sn))`. We can split the array of strings into two halves, find the LCP for each half recursively, and then find the LCP of the two resulting strings. This process continues until we are left with subproblems of a single string, where the LCP is the string itself. The results are then merged back up the recursion tree.

```java
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        return longestCommonPrefix(strs, 0, strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        } else {
            int mid = l + (r - l) / 2;
            String lcpLeft = longestCommonPrefix(strs, l, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    String commonPrefix(String left, String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if (left.charAt(i) != right.charAt(i)) {
                return left.substring(0, i);
            }
        }
        return left.substring(0, min);
    }
}
```
### Algorithm
- Define a recursive function, say `lcp(strs, left, right)`, that finds the LCP for the subarray `strs[left...right]`.
- The base case for the recursion is when `left == right`. In this case, there is only one string, so the LCP is the string itself. Return `strs[left]`.
- In the recursive step, divide the current array range into two halves by finding the middle index `mid = (left + right) / 2`.
- Make two recursive calls: one for the left half, `lcpLeft = lcp(strs, left, mid)`, and one for the right half, `lcpRight = lcp(strs, mid + 1, right)`.
- Once the results from both halves are returned, combine them by finding the common prefix of `lcpLeft` and `lcpRight`. This can be done with a helper function that compares two strings character by character.
- The result of this combination is the LCP for the range `[left, right]`.

## Horizontal Scanning
This is a straightforward, iterative approach. We assume the first string in the array is the longest common prefix and then, for each subsequent string, we shorten our candidate prefix until it matches the start of that string. This process is repeated for all strings in the array.
**Time:** O(S) · **Space:** O(1)
**Pros:** Easy to understand and implement.; Excellent space efficiency, using only constant extra space.
**Cons:** Can be inefficient if the strings are long and the common prefix is short. It may perform many redundant string comparisons and substring operations.
### Explanation
We begin by taking the first string as our initial guess for the longest common prefix. Then, we iterate through the remaining strings one by one. For each string, we compare it against our current prefix. If the string doesn't start with the prefix, we trim the last character from our prefix and check again. We continue this trimming process until the prefix is a valid prefix for the current string. If our prefix ever becomes an empty string, we know no common prefix exists and can stop early. After checking all the strings, whatever remains of our initial guess is the final answer.

```java
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}
```
### Algorithm
- If the input array is empty or null, return an empty string `""`.
- Initialize a variable `prefix` with the first string of the array, `strs[0]`.
- Iterate through the array from the second string (`i = 1`) to the end.
- For each string `strs[i]`, check if it starts with the current `prefix`. A `while` loop with `strs[i].indexOf(prefix) != 0` can be used for this.
- If `strs[i]` does not start with `prefix`, shorten the `prefix` by removing its last character: `prefix = prefix.substring(0, prefix.length() - 1)`.
- Repeat this until `prefix` is a prefix of `strs[i]` or it becomes empty.
- If `prefix` becomes empty, it means there is no common prefix, so we can return `""` immediately.
- After the outer loop finishes, the remaining `prefix` is the longest common prefix for all strings.

## Vertical Scanning
This approach compares characters vertically, or column by column. Instead of comparing entire strings at a time, we compare the characters at the first position for all strings, then the second position, and so on. The process stops as soon as a column of characters is not identical, or one of the strings runs out of characters.
**Time:** O(S) · **Space:** O(1)
**Pros:** Extremely efficient in terms of both time and space.; Often performs the minimum number of character comparisons required.; Terminates as soon as the first character mismatch is found, leading to excellent performance on average.
**Cons:** While generally optimal, the worst-case time complexity is the same as horizontal scanning.
### Explanation
The vertical scanning method is one of the most efficient ways to solve this problem. We iterate through the characters of the first string from left to right. For each character, we then scan down through all the other strings to ensure they have the same character at the same position. If we find any string that either doesn't have a character at that position or has a different character, we know the longest common prefix is the substring we've successfully matched up to that point. This allows for an early exit and avoids unnecessary comparisons, making it very fast in practice, especially when the common prefix is short.

```java
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}
```
### Algorithm
- If the input array is empty or null, return `""`.
- Iterate through the characters of the first string, `strs[0]`, using an index `i` from `0` to `strs[0].length() - 1`.
- For each character `c` at index `i` in the first string:
  - Start an inner loop to iterate through all other strings in the array, from `j = 1` to `strs.length - 1`.
  - In the inner loop, check for two mismatch conditions for the string `strs[j]`:
    1. The index `i` is out of bounds for `strs[j]` (i.e., `i == strs[j].length()`).
    2. The character at `strs[j].charAt(i)` is not equal to `c`.
  - If either condition is true, it means the common prefix ends at index `i-1`. Return the prefix found so far, which is `strs[0].substring(0, i)`.
- If the outer loop completes without finding any mismatches, it means the entire first string is a common prefix. In this case, return `strs[0]`.

# Solutions
### CSharp

```csharp
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 ]; } }
```

### Java

```java
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 (strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) {
          return strs[0].substring(0, i);
        }
      }
    }
    return strs[0];
  }
}

```

### JavaScript

```javascript
/** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function ( strs ) { for ( let j = 0 ; j < strs [ 0 ]. length ; j ++ ) { for ( let i = 0 ; i < strs . length ; i ++ ) { if ( strs [ 0 ][ j ] !== strs [ i ][ j ]) { return strs [ 0 ]. substring ( 0 , j ); } } } return strs [ 0 ]; };
```

### CPP

```cpp
class Solution {
public:
  string longestCommonPrefix(vector<string> &strs) {
    int n = strs.size();
    for (int i = 0; i < strs[0].size(); ++i) {
      for (int j = 1; j < n; ++j) {
        if (strs[j].size() <= i || strs[j][i] != strs[0][i]) {
          return strs[0].substr(0, i);
        }
      }
    }
    return strs[0];
  }
};

```

### Python

```python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str: for i in range(len(strs[0])): for s in strs[1:]: if len(s) <= i or s[i] != strs[0][i]: return s[: i] return strs[0]

```