Home » Interview coding problems/challenges

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

IF anyone is empty string
    return empty string;

2. Declare result as an empty string;

    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

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

---