A **prefix** is a collection of characters at the beginning of a string. For instance, "mi" is a prefix of "mint" and the longest common prefix between "mint", "mini", and "mineral" is "min".

## Algorithm

1. Sort the array of strings in alphabetical order.

2. Compare the characters in the first and last strings in the array. Since the array is sorted, common characters among the first and last element will be common among all the elements of the array.

   2.1. If they are same, then append the character to the `result`.

   2.2. Else, stop the comparison -- `result` contains the longest common prefix among the strings in the array. 

The following illustration shows the algorithm in action:

#include <iostream>
#include <string>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  string arr[3] = {"mint", "mini", "mineral"}; 
  int size = sizeof(arr)/sizeof(*arr);
  // The longest common prefix of an empty array is "".
  if (size == 0){
    cout << "Longest common prefix:" << "" <<endl;
  }
    // The longest common prefix of an array containing 
    // only one element is that element itself.
  else if (size == 1){
    cout << "Longest common prefix:" << arr[0] <<endl;
  }
  else{
    // Sort the array
    std::sort(arr, arr + size);
    int length = arr[0].size();
    string result = "";
    // Compare the first and the last string character
    // by character.
    for(int i = 0; i < length; i++){
      // If the characters match, append the character to the result.
      if(arr[0][i] == arr[size-1][i]){
        result += arr[0][i];
      }
      // Else stop the comparison.
      else{
        break;
      }
    }
    cout << "Longest common prefix: " << result <<endl; 
  }
  return 0;
}

arr = ["mint", "mini", "mineral"]
# The longest common prefix of an empty array is "".
if not arr:
  print("Longest common prefix:", "")
# The longest common prefix of an array containing 
# only one element is that element itself.
elif len(arr) == 1:
  print("Longest common prefix:", arr[0])
else:
  # Sort the array
  arr.sort()
  result = ""
  # Compare the first and the last string character
  # by character.
  for i in range(len(arr[0])):
      #  If the characters match, append the character to
      #  the result.
      if arr[0][i] == arr[-1][i]:
          result += arr[0][i]
      # Else, stop the comparison
      else:
          break
  print("Longest common prefix:", result)

Python3

import java.util.*;
class HelloWorld {
    public static void main(String args[]) {
        String[] arr = {"mint", "mini", "mineral"};
        int size = arr.length;
        // The longest common prefix of an empty array is "".
        if (size == 0){
          System.out.println("Longest common prefix: "); 
        }
        // The longest common prefix of an array containing 
        // only one element is that element itself.
        else if (size == 1){
          System.out.println("Longest common prefix: " + arr[0]);
        }
        else{
          // Sort the array
           Arrays.sort(arr);
           int length = arr[0].length();
           StringBuilder res = new StringBuilder();
           // Comapre the first and the last strings character
           // by character.
           for(int i = 0; i < length; i++){
             // If the characters match, append the character to the result.
             if(arr[0].charAt(i) == arr[size - 1].charAt(i)){
               res.append(arr[0].charAt(i));
             }
             // Else, stop the comparison.
             else{
               break;
             }
           }
           String result = res.toString();
           System.out.println("Longest common prefix: " + result);
        } 
    }
}

How to find the longest common prefix in an array of strings

Algorithm

Implementation