# Longest Common Prefix

In this article, we are going to see how to find longest common prefix from a set of strings? This problem can be featured in any interview coding round.
Submitted by Radib Kar, on January 09, 2019

Problem statement:

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 "".

Solution:

Input Example:

```    Example 1:
Let the set of strings to be {"flower", "fly", "flow"}
The longest common prefix is "fl"

Example 2:
Let the set of strings to be {"dog", "donkey", "door", "cat"}
The longest common prefix is "", i.e., empty string.
Since there is no common prefix at all.
```

## Longest common prefix

Longest common prefix simply means the longest prefix (prefix is a substring also, but not vice-versa) all the member strings consist of.

### Algorithm to find longest common prefix of a set of strings

Solving particularly for two string, the problem is not that difficult what it is for a set of strings. But we can simply break the problem into sub-problems where we can solve for only two strings and simply pass the output for further string processing 's. In a simple word, the whole thing can be formulated to be:

```    LongestCommonPrefix(string1, string2, ..., string n)
=   LongestCommonPrefix(LongestCommonPrefix(string1,string2),string3,...,string n)
=   LongestCommonPrefix(newstring1,string3,string4,...,string n)
=   ...
=   LongestCommonPrefix(newstring n-1, string n)
=   new string n = final result

So this simply converts the problem for a set of
strings to a problem of two strings only
```

Finding longest common prefix for two strings (string x, string y)

1. Check for base case
2. ```IF anyone is empty string
return empty string;
```
3. Declare result as an empty string;
4. ```    IF string x is smaller than y
//check for common prefix part on basis of x
FOR( i=0;i<length of string x; i++)
IF(x[i]==y[i])
result+=x[i]; //append the common character
ELSE//no common character at this point
Returnresult
END FOR

ELSE//if string y is smaller than x
//check for common prefix part on basis of y
FOR (i=0;i<length of y; i++)
IF(y[i]==x[i])
result+=y[i];//append the common character
ELSE//no common character at this point
return result;
END FOR
END IF-ELSE
```
5. result consist of longest common prefix for these two strings

Explanation with example

```    Let's consider the first example
The set of strings: {"flower", "fly", "flow"}
LongestCommonPrefix("flower", "fly", "flow")
=   LongestCommonPrefix(LongestCommonPrefix ("flower","fly"),"flow")
=   LongestCommonPrefix("fl", "flow")
=   "fl"

Let's consider the second example
the set of strings to be {"dog", "donkey", "door", "cat"}
LongestCommonPrefix("dog", "donkey", "door", "cat")
=   LongestCommonPrefix(LongestCommonPrefix ("dog", "donkey"),"door", "cat")
=   LongestCommonPrefix("do","door", "cat")
=   LongestCommonPrefix (LongestCommonPrefix("do", "door") , "cat")
=   LongestCommonPrefix("do", "cat")
=   "" //empty string
```

C++ implementation

```#include <bits/stdc++.h>
using namespace std;

string findPrefix(string x,string y){
//base case checking
if(x=="" || y=="")
return "";

string result="";

//if string x is smaller than y
if(x.length()<y.length()){
//check up for common prefix part
for(int i=0;i<x.length();i++){
if(x[i]==y[i])
result+=x[i];
}
}
else{
//if string y is smaller than x
for(int i=0;i<y.length();i++){
//check up for common prefix part
if(y[i]==x[i])
result+=y[i];
else
return result;
}
}
return result;
}

string longestCommonPrefix(vector<string>& strs) {
//base cases
if(strs.size()==0)
return "";
//if only one string exists
if(strs.size()==1)
return strs;
string prefix=strs;
//follow the associative property for checking
//take two strings each time & pass output prefix
//as one string for further processings
for(int i=1;i<strs.size();i++){
prefix=findPrefix(prefix,strs[i]);
if(prefix=="")
return prefix;
}
return prefix;
}

int main(){
int n;
cout<<"enter no of strings you want to add\n";
cin>>n;

string s;
vector<string> v;
cout<<"enter "<<n<<" strings\n";

//collect input
while(n--){
cin>>s;
v.push_back(s);
}
//print longest common prefix
if(longestCommonPrefix(v)=="")
cout<<"no common prefix between the strings\n";
else
cout<<"longest common prefix: "<<longestCommonPrefix(v)<<endl;

return 0;
}
```

Output

```First run:
enter no of strings you want to add
3
enter 3 strings
flower
fly
flow
longest common prefix: fl

Second run:
enter no of strings you want to add
4
enter 4 strings
dog
donkey
door
cat
no common prefix between the strings
```