Home » Technical Interview Questions » String Interview Questions » Longest common prefix (word by word)

Longest common prefix (word by word)

Reading Time - 2 mins

In the given input set of strings, write a program to find the longest common prefix.


Input strings : {“code”, ”codex”, ”cosec”, ”coding”,”cobalt”}

Output : “co”

Time complexity : O(NM),

N = Number of strings
M = Length of longest string

Space complexity : O(M)


Here, we use associate property

LCP(s1, s2, s3) = LCP(LCP(s1, s2), s3)

1.  We create a function to find common prefix for two strings.
a. Compare strings characters.
b. Push them to result, if same.
c. Return final result.

2. Make initial output_prefix as first element of input array.

3. Compare it to second it and store it in ouput_prefix and soon.

4. Return the final output_prefix.

C++ Program

#include <bits/stdc++.h>

using namespace std;
//function to find
//common prefix of two strings
string LCPUtil(string string1, string string2)
    string output;
    int length1 = string1.length(), length2 = string2.length();
    //Compare string1 and string2
    for (int i=0, j=0; (i<=length1-1) && (j<=length2-1); i++,j++)
        if (string1[i] != string2[j])
        output.push_back(string1[i]); }
    return (output);
//Function to find LCP
//longest commmon prefix compare word by word 
string  LCP(string arr[], int n)
    string output_prefix =  arr[0];
    for (int i=1; i<=n-1; i++)
        output_prefix = LCPUtil(output_prefix, arr[i]);
    return (output_prefix);
//Main function
int main()
    string string_array[] = {"code","codex", "cosec", "coding","cobalt"};
    int length = sizeof(string_array)/sizeof(string_array[0]);
    string ans = LCP(string_array, length);
        cout<<"Longest common prefix is: "<<ans;
        cout<<"No common prefix found";
    return 0;

Try It


READ  String Compression
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions