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

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


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++)
    		    result+=x[i]; //append the common character
    			    ELSE//no common character at this point
    		    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++)
    		    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
		//check up for common prefix part
		for(int i=0;i<x.length();i++){
		//if string y is smaller than x
		for(int i=0;i<y.length();i++){
			//check up for common prefix part 
				return result;
	return result;

string longestCommonPrefix(vector<string>& strs) {
	//base cases
		return "";
	//if only one string exists
		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++){
			return prefix;
	return prefix;

int main(){
	int n;
	cout<<"enter no of strings you want to add\n";
	string s;
	vector<string> v;
	cout<<"enter "<<n<<" strings\n";
	//collect input
	//print longest common prefix
		cout<<"no common prefix between the strings\n";
		cout<<"longest common prefix: "<<longestCommonPrefix(v)<<endl;

	return 0;


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

Second run:
enter no of strings you want to add
enter 4 strings
no common prefix between the strings

Comments and Discussions

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.