Longest Common Prefix (Using Biary Search)

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”}


Algorithm(using Binary search)

1. Find the string which has the minimum length(let it be L), and perform binary search on any one of the string from input array where Low = 0 and High = L-1

2. If all the characters in left half are present at the corresponding indexes, then add the characters to the output stirng and search in right half to find the longer prefix

3. Else, If the charcaters in left half is not present in correspondng indexes then there is no need to search in right half. But, keep searching in left half(ie, start index to mid index)

C++ Program

using namespace std;
// finds the minimum length
int minLength(string arr[], int n)
    int min = INT_MAX;
    for (int i=0; i<=n-1; i++)
        if (arr[i].length() < min)
            min = arr[i].length();
//checks if the input array contains this prefix 
bool checkPrefix(string arr[], int n, string str,
                       int start, int end)
    for (int i=0; i<=n-1; i++)
        for (int j=start; j<=end; j++)
            if (arr[i][j] != str[j])
                return (false);
    return (true);
// returns the longest common prefix
string longestCommonPrefix(string arr[], int n)
    int index = minLength(arr, n);
    string prefix; // Our resultant string
    //Binary search
    int low = 0, high = index;
    while (low <= high)
        int mid = low + (high - low) / 2;
        if (checkPrefix (arr, n, arr[0], low, mid))
            // If all the strings in the input array contains
            // this prefix then append this substring to
            // our answer
            prefix = prefix + arr[0].substr(low, mid-low+1);
            // right part
            low = mid + 1;
        else // Go for the left part
            high = mid - 1;
    return (prefix);

int main()
    string arr[] = {"boyfriend", "boy", "bo"};
    int n = sizeof (arr) / sizeof (arr[0]);
    string ans = longestCommonPrefix(arr, n);
    if (ans.length())
        cout << "The longest common prefix is "<< ans<<endl;
        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