×

# 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 [Last updated : March 20, 2023]

## Problem Description

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 of Longest Common Prefix

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 for Longest Common Prefix

```#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[0];
string prefix = strs[0];
//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
```