Longest Common Prefix (Using Divide and Conquer)

Given a array of strings, write a function that will print the longest common prefix If there is no common prefix then print “No Common Prefix”


arr[] = {“boy”, ‘boyfriend”, “bo”}


Time Complexity : O(mn), where m is the length of the largest string and n is the numbe rof strings


1. Recursively divide the array of strings into two parts until length becomes 1

2. Now, start conquering by returning the common prefix of the left and right strings

C++ Program

using namespace std;
//Finds the common prefix between two strings
string commonPrefix(string s1, string s2)
    string result;
    int n1 = s1.length(), n2 = s2.length();
    for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)
        if (s1[i] != s2[j])
    return (result);
//returns the prefix of the longest common prefix, recursisve functio
string longestCommonPrefix(string arr[], int low, int high)
    if (low == high)
        return (arr[low]);
    if (high > low)
        int mid = low + (high - low) / 2;
        string s1 = longestCommonPrefix(arr, low, mid);
        string s2 = longestCommonPrefix(arr, mid+1, high);
        return (commonPrefix(s1, s2));

int main()
    string arr[] = {"boyfriend", "bo", "boy"};
    int n = sizeof (arr) / sizeof (arr[0]);
    string ans = longestCommonPrefix(arr, 0, n-1);
    if (ans.length())
        cout << "The longest common prefix is "
             << ans;
        cout << "There is no common prefix";
    return (0);

Try It


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions