Longest Common Prefix using Binary Search

Given an array of strings arr[], the task is to return the longest common prefix among each and every strings present in the array. If there’s no prefix common in all the strings, return "".

Examples:

Input: arr[] = [“geeksforgeeks”, “geeks”, “geek”, “geezer”]
Output: "gee"
Explanation: "gee" is the longest common prefix in all the given strings: "geeksforgeeks", "geeks", "geeks" and "geezer".

Input: arr[] = ["apple", "ape", "april"]
Output : "ap"
Explanation: "ap" is the longest common prefix in all the given strings: "apple", "ape" and "april".

Input: arr[] = ["hello", "world"]
Output: ""
Explanation: There’s no common prefix in the given strings.

Approach:

The idea is to use binary search on the indices to find the length of longest common prefix.

We can observe that the length of common prefix cannot be greater than the length of smallest string in given set of strings. So the search space for binary search will be from 0 to length of smallest string - 1.

In each iteration of binary search [low to high], we will check whether the prefix [low to mid] is common among all strings or not.

• If the prefix is common among all string then check for larger length prefix by updating low = mid + 1
• Else check for smaller length prefix, by updating high = mid - 1.

Note: Instead of checking each character from 0 to mid, we will to check only substring from low to mid because substring from 0 to low would have been checked in previous iterations and found to be common.

// C++ program to find the longest common prefix // using Binary Search #include <iostream> #include <vector> using namespace std; // Function to check if the substring between the  // indexes[left ... right] was common among all strings or not bool allContainSubstring(vector<string>& arr, int left,   int right) {    for (int i = 1; i <= arr.size() - 1; i++) {  for (int j = left; j <= right; j++) {  if (arr[i][j] != arr[0][j])  return false;  }  }    return true; } // A Function that returns the longest common prefix // from the array of strings string longestCommonPrefix(vector<string>& arr) {  int minLen = arr[0].length();  // Find length of shortest string  for (int i = 1; i < arr.size(); i++)  minLen = min(minLen, (int) arr[i].length());  // We will do an in-place binary search on the indices  // to find the length of longest common prefix  int lo = 0, hi = minLen - 1;  int prefixLen = 0;  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (allContainSubstring(arr, lo, mid)) {    // If all the strings in the input array  // contains common prefix till mid index  // then update prefixLen with mid + 1   prefixLen = mid + 1;  // And then check in the right part  lo = mid + 1;  }   // Otherwise check in the left part  else   hi = mid - 1;  }  // return the common prefix by taking   // substring from first string   return arr[0].substr(0, prefixLen); } int main() {  vector<string> arr = {"geeksforgeeks", "geeks",   "geek", "geezer"};    cout << longestCommonPrefix(arr) << endl;  return 0; } 

// Java program to find the longest common prefix // using Binary Search import java.util.List; class GfG {  // Function to check if the substring between the   // indexes[left ... right] was common among all strings or not  static boolean allContainSubstring(String[] arr, int left,   int right) {  for (int i = 1; i < arr.length; i++) {  for (int j = left; j <= right; j++) {  if (arr[i].charAt(j) != arr[0].charAt(j)) {  return false;  }  }  }  return true;  }  // A Function that returns the longest common prefix  // from the array of strings  static String longestCommonPrefix(String []arr) {  int minLen = arr[0].length();  // Find length of shortest string  for (String str : arr) {  minLen = Math.min(minLen, str.length());  }  // We will do an in-place binary search on the indices  // to find the length of longest common prefix  int lo = 0, hi = minLen - 1;  int prefixLen = 0;  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (allContainSubstring(arr, lo, mid)) {  // If all the strings in the input array  // contain common prefix till mid index  // then update prefixLen with mid + 1   prefixLen = mid + 1;  // And then check in the right part  lo = mid + 1;  }   else {    // Otherwise check in the left part  hi = mid - 1;  }  }  // Return the common prefix by taking   // substring from the first string   return arr[0].substring(0, prefixLen);  }  public static void main(String[] args) {  String[] arr = {"geeksforgeeks", "geeks", "geek",   "geezer"};  System.out.println(longestCommonPrefix(arr));  } } 

# Python program to find the longest common prefix # using Binary Search # Function to check if the substring between the  # indexes[left ... right] was common among all strings or not def allContainSubstring(arr, left, right): for i in range(1, len(arr)): for j in range(left, right + 1): if arr[i][j] != arr[0][j]: return False return True # A Function that returns the longest common prefix # from the array of strings def longestCommonPrefix(arr): minLen = len(arr[0]) # Find length of shortest string for s in arr: minLen = min(minLen, len(s)) # We will do an in-place binary search on the indices # to find the length of longest common prefix lo, hi = 0, minLen - 1 prefixLen = 0 while lo <= hi: mid = lo + (hi - lo) // 2 if allContainSubstring(arr, lo, mid): # If all the strings in the input array # contain common prefix till mid index # then update prefixLen with mid + 1  prefixLen = mid + 1 # And then check in the right part lo = mid + 1 else: # Otherwise check in the left part hi = mid - 1 # Return the common prefix by taking  # substring from the first string  return arr[0][:prefixLen] if __name__ == "__main__": arr = ["geeksforgeeks", "geeks", "geek", "geezer"] print(longestCommonPrefix(arr)) 

// C# program to find the longest common prefix // using Binary Search using System; using System.Collections.Generic; class GfG {  // Function to check if the substring between the   // indexes [left ... right] was common among all strings or not  static bool allContainSubstring(string[] arr,   int left, int right) {  for (int i = 1; i < arr.Length; i++) {  for (int j = left; j <= right; j++) {  if (arr[i][j] != arr[0][j])   return false;  }  }  return true;  }  // A Function that returns the longest common prefix  // from the array of strings  static string longestCommonPrefix(string[] arr) {  int minLen = arr[0].Length;  // Find length of shortest string  foreach (string str in arr) {  minLen = Math.Min(minLen, str.Length);  }  // We will do an in-place binary search on the indices  // to find the length of longest common prefix  int lo = 0, hi = minLen - 1;  int prefixLen = 0;  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (allContainSubstring(arr, lo, mid)) {    // If all the strings in the input array  // contain common prefix till mid index  // then update prefixLen with mid + 1   prefixLen = mid + 1;  // And then check in the right part  lo = mid + 1;  }   else {    // Otherwise check in the left part  hi = mid - 1;  }  }  // Return the common prefix by taking   // substring from the first string   return arr[0].Substring(0, prefixLen);  }  static void Main() {  string[] arr = {"geeksforgeeks", "geeks", "geek",   "geezer"};  Console.WriteLine(longestCommonPrefix(arr));  } } 

// JavaScript program to find the longest common prefix // using Binary Search // Function to check if the substring between the  // indexes [left ... right] was common among all strings or not function allContainSubstring(arr, left, right) {  for (let i = 1; i < arr.length; i++) {  for (let j = left; j <= right; j++) {  if (arr[i][j] !== arr[0][j])   return false;  }  }  return true; } // A Function that returns the longest common prefix // from the array of strings function longestCommonPrefix(arr) {  let minLen = arr[0].length;  // Find length of shortest string  for (let str of arr) {  minLen = Math.min(minLen, str.length);  }  // We will do an in-place binary search on the indices  // to find the length of longest common prefix  let lo = 0, hi = minLen - 1;  let prefixLen = 0;  while (lo <= hi) {  const mid = lo + Math.floor((hi - lo) / 2);  if (allContainSubstring(arr, lo, mid)) {    // If all the strings in the input array  // contain common prefix till mid index  // then update prefixLen with mid + 1   prefixLen = mid + 1;  // And then check in the right part  lo = mid + 1;  }   else {    // Otherwise check in the left part  hi = mid - 1;  }  }  // Return the common prefix by taking   // substring from the first string   return arr[0].substring(0, prefixLen); } // Driver Code const arr = ["geeksforgeeks", "geeks",  "geek", "geezer"]; console.log(longestCommonPrefix(arr)); 

gee 

Time Complexity : O(n*m), where n is number of strings and m is length of shortest string. The recurrence relation is: T(m) = T(m/2) + O(n*(m/2)). Upon solving, we get time complexity of O(n*m).

Auxiliary Space: O(m), to store the longest prefix string.

Other Approaches:

• Longest Common Prefix using Sorting
• Longest Common Prefix Word by Word Matching
• Longest Common Prefix Character by Character Matching
• Longest Common Prefix Divide and Conquer
• Longest Common Prefix Using Trie