# Longest Common Prefix (With Solution)

## Problem Statement

Given the array of strings S[], you need to find the longest string S which is the prefix of ALL the strings in the array.

Longest common prefix (LCP) for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.

For Example: longest common prefix of “abcdefgh” and “abcefgh” is “ABC”.

Examples:

Input: S[] = {“abcdefgh”, “abcefgh”}
Output: “abc”
Explanation: Explained in the image description above

Input: S[] = {“abcdefgh”, “aefghijk”, “abcefgh”}
Output: “a”

## Horizontal Scanning Approach

The idea is to horizontally scan all the characters of the array of strings one by one and find the Longest Common Prefix among them. The LCP can be obtained as follows –

LCP(S1…SN) = LCP(LCP(LCP(S1, S2), S3),…., SN)

Algorithm

• Iterate through the string one by one from S1 till SN.
• For each iteration till ith index, the LCP(S1…Si) can be obtained.
• In case, the LCP is an empty string, terminate loop and return the empty string.
• Else, continue and after scanning of N strings, the LCP(S1…SN) can be obtained.

### C++ Implementation Horizontal Scanning

```string longestCommonPrefix(vector<string>& S) {
if (S.size() == 0) return "";
std::string prefix = S;

for (int i = 1; i < S.size(); ++i) {
std::string s = S[i];
if (s.size() == 0 || prefix == "") return "";
prefix = prefix.substr(0, std::min(prefix.size(), s.size()) );

for (int k = 0; k < s.size() && k < prefix.size(); ++k) {
if (s[k] != prefix[k]) {
prefix = prefix.substr(0, k);
break;
}
}
}
return prefix;
}```

### Java Implementation Horizontal Scanning

``` public String longestCommonPrefix(String[] S) {
if (S.length == 0) return "";
String prefix = S;
for (int i = 1; i < S.length; i++)
while (S[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}```

### Python Implementation Horizontal Scanning

```def longestCommonPrefix(self, S):
if "" in S or S == []:
return ""
preix = S
for i in range(1,len(S)):
while(preix != ""):
try:
if str.index(str(S[i]),preix) == 0:
break
else:
preix = preix[:-1]
except:

preix = preix[:-1]
return preix```

Time Complexity: O(N) where N is the size of the array S[].
Space Complexity: O(1), as no extra space is used.

## Vertical Scanning Approach

The idea is to scan and compare the characters from top to bottom of the ith index for each string.

This approach is efficient in cases when the LCP string is very small. Hence, we do not need to perform K comparisons.

Algorithm

• Iterate through the string one by one from S1 till SN.
• Start comparing the 0th index, 1st index … ith index simultaneously for each string.
• In case, any of the ith index characters doesn’t match, terminate the algorithm and return the LPS(1,i)
• Else, continue and after scanning of N strings, the LCP(S1…SN) can be obtained.

### C++ Implementation of Vertical Scanning

```string longestCommonPrefix(vector<string> S) {
if (S.size() == 0) return "";
for (int i = 0; i < S.length() ; i++){
char c = S[i];
for (int j = 1; j < S.length; j ++) {
if (i == S[j].length() || S[j][i] != c)
return S.substr(0, i);
}
}
return S;
}```

### Java Implementation of Vertical Scanning

```public String longestCommonPrefix(String[] S) {
if (S == null || S.length == 0) return "";
for (int i = 0; i < S.length() ; i++){
char c = S.charAt(i);
for (int j = 1; j < S.length; j ++) {
if (i == S[j].length() || S[j].charAt(i) != c)
return S.substring(0, i);
}
}
return S;
}```

### Python Implementation of Vertical Scanning

```def longestCommonPrefix(S) {
if (len(S) == 0) return "";
for i in range(len(S)):
c = S[i];
for j in range(len(S)):
if i == len(S[j]) or  S[j][i] != c)
return S[0:i];
}
}
return S;
}```

Time Complexity: O(K) where K is the sum of all the characters in all strings.
Space Complexity: O(1), as no extra space is used.

## Divide and Conquer Approach

The approach is to divide the given array of strings into various subproblems and merge them to get the LCP(S1..SN).

First, divide the given array into two parts. Then, in turn, divide the left and right array obtained into two parts and recursively keep dividing them, until they cannot be divided further.

Mathematically,LCP(S1….SN) = LCP(S1….Sk) + LCP(Sk+1…SN), where LCP(S1..SN) is the LCP of the array of strings and 1 < k < N.

Algorithm:

• Recursively divide the input array of strings into two parts.
• For each division, find the LCP obtained so far.
• Merge the obtained LCP from both the subarrays and return it.
• I.e. LCP(LCP(S[left…mid], LCP(S[mid + 1, right])) and return it.

### C++ Implementation

```string commonPrefixUtil(string str1, string str2)
{
string result;
int n1 = str1.length(), n2 = str2.length();

for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)
{
if (str1[i] != str2[j])
break;
result.push_back(str1[i]);
}
return (result);
}
string longestCommonPrefix(string S[], int low, int high)
{
if (low == high)
return (S[low]);

if (high > low)
{
int mid = low + (high - low) / 2;

string str1 = commonPrefix(S, low, mid);
string str2 = commonPrefix(S, mid+1, high);

return (commonPrefixUtil(str1, str2));
}
}```

### Java Implementation

```static String commonPrefixUtil(String str1, String str2) {
String result = "";
int n1 = str1.length(), n2 = str2.length();

for (int i = 0, j = 0; i <= n1 - 1 &&
j <= n2 - 1; i++, j++) {
if (str1.charAt(i) != str2.charAt(j)) {
break;
}
result += str1.charAt(i);
}
return (result);
}
static String longestCommonPrefix(String S[], int low, int high) {
if (low == high) {
return (S[low]);
}

if (high > low) {
int mid = low + (high - low) / 2;

String str1 = commonPrefix(S, low, mid);
String str2 = commonPrefix(S, mid + 1, high);

return (commonPrefixUtil(str1, str2));
}
return null;
}```

### Python Implementation

```def commonPrefixUtil(str1, str2):

result = ""
n1, n2 = len(str1), len(str2)
i, j = 0, 0

while i <= n1 - 1 and j <= n2 - 1:

if str1[i] != str2[j]:
break
result += str1[i]
i, j = i + 1, j + 1

return result

def longestCommonPrefix(S, low, high):

if low == high:
return S[low]

if high > low:
mid = low + (high - low) // 2

str1 = commonPrefix(S, low, mid)
str2 = commonPrefix(S, mid + 1, high)

return commonPrefixUtil(str1, str2)```

Time Complexity: O(K) where K is the sum of all the characters in all strings.
Space Complexity: O(M log N), as there are log N recursive calls and each needs a space of M.

## Binary Search Approach

Another way to approach the problem is to use the concept of Binary Search.

Algorithm:

• Consider the string with the smallest length. Let the length be L.
• Consider a variable low = 0 and high =  L – 1.
• Perform binary search:
• Divide the string into two halves, i.e. low – mid and mid + 1 to high.
• Compare the substring upto the mid of this smallest string to every other character of the remaining strings at that index.
• If the substring from 0 to mid – 1 is common among all the substrings, update low with mid + 1, else update high with mid – 1
• If low == high, terminate the algorithm and return the substring from 0 to mid.

### C++ Implementation of Binary Search Approach

```int findMinLength(string S[], int n)
{
int min = INT_MAX;

for (int i=0; i<=n-1; i++)
if (S[i].length() < min)
min = S[i].length();
return(min);
}

bool allContainsPrefix(string S[], int n, string str,
int start, int end)
{
for (int i=0; i<=n-1; i++)
for (int j=start; j<=end; j++)
if (S[i][j] != str[j])
return (false);
return (true);
}
string longestCommonPrefix(string S[], int n)
{
int index = findMinLength(S, n);
string prefix;
int low = 0, high = index;

while (low <= high)
{
int mid = low + (high - low) / 2;

if (allContainsPrefix (S, n, S, low, mid))
{
prefix = prefix + S.substr(low, mid-low+1);
low = mid + 1;
}

else
high = mid - 1;
}

return (prefix);
}```

### Java Implementation of Binary Search Approach

```static int findMinLength(String S[], int n)
{
int min = Integer.MAX_VALUE;
for (int i = 0; i <= (n - 1); i++)
{
if (S[i].length() < min) {
min = S[i].length();
}
}
return min;
}

static boolean allContainsPrefix(String S[], int n,
String str, int start, int end)
{
for (int i = 0; i <= (n - 1); i++)
{
String S_i = S[i];

for (int j = start; j <= end; j++)
if (S_i.charAt(j) != str.charAt(j))
return false;
}
return true;
}

static String longestCommonPrefix(String S[], int n)
{
int index = findMinLength(S, n);
String prefix = "";
int low = 0, high = index-1;
while (low <= high) {
int mid = low + (high - low) / 2;

if (allContainsPrefix(S, n, S, low,
mid))
{
prefix = prefix + S.substring(low, mid + 1);
low = mid + 1;
}
else
{
high = mid - 1;
}
}

return prefix;
}```

### Python Implementation of Binary Search Approach

```def findMinLength(strList):
return len(min(S, key = len))

def allContainsPrefix(strList, str,
start, end):
for i in range(0, len(strList)):
word = strList[i]
for j in range(start, end + 1):
if word[j] != str[j]:
return False
return True

def longestCommonPrefix(strList):
index = findMinLength(strList)
prefix = ""

low, high = 0, index - 1
while low <= high:
mid = int(low + (high - low) / 2)
if allContainsPrefix(strList,
strList, low, mid):

prefix = prefix + strList[low:mid + 1]

low = mid + 1
else:
high = mid - 1

return prefix```

Time Complexity: O(K. logN) where K is the sum of all the characters in all strings.
Space Complexity: O(1)

## Practice Question

Longest Common Prefix

What is the best time and space complexity of finding the longest prefix string?
The best time complexity is O(N) and the space complexity is O(1) using the horizontal and vertical scanning approach.

Is the binary search approach better than the other approaches?
No, the binary search takes O(K*logN) time complexity. Hence, it is not the most efficient approach.

##### Previous Post ## Longest Common Substring

##### Next Post ## Rearrange Array Alternately

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡