# Find Longest Common Prefix

Solving any problem requires one to analyze various available solutions and then look at factors like space complexity, time complexity, and ease of development.

Problem statement: Find the longest common prefix from N number of Strings.

Example: “kamal”, “kamalmeet”, “kamaljeet” should return “kamal”

## Solution 1- Vertical Scanning

Approach: Start with the first element of each string and compare for equality. Continue till a point we do not find the same character.

Pseudo code:

```-- for i=0 to n, of the length of the first (any) string
---- check if ith character is equal for all string
------ if not, return string from 0 to i-1 character```

Code:

``````    public String longestCommonPrefix(String[] strs) {
for (int index = 0; index < strs[0].length(); index++) {
char ch = strs[0].charAt(index);
for (String st : strs) {
// one of the strings has ended or char mismatch found
if (index >= st.length() || st.charAt(index) != ch) {
return strs[0].substring(0, index);
}
}
}
// if you reached here, first string is longest common prefix
return strs[0];
}``````

Time Complexity: O(S) for Worst case all strings are equal, and S is the sum of all string lengths

Space Complexity: O(1) no additional data structure

## Solution 2 – Horizontal Scanning

Approach: Start by comparing the first two strings and find the longest common prefix. Use this as input and compare it with next string and so on.

Pseudo code:

```-- longestprefix = str[0]
-- for strings in i=1 to N
---- longestprefix = findlongestprefix(longestprefix, str[i])
-- return longestprefix```

Time Complexity: O(S)

Space complexity: O(1)

## Solution 3- Divide and Conquer

Approach: Break down the array of strings into two equal parts, solve for the two subarrays, and find a solution for two results (repeat the process at each step).