Longest Common Prefix using Sorting  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg eBay Facebook Google Microsoft
String

In the Longest Common Prefix using Sorting problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings.

Example  

Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”}
Output: "tu"

Input2: {"baggage", "banana", "batsmen"}
Output: "ba"

Input3: {"abcd"}
Output: "abcd"

Input4: {"customer","custard"}
Output: "cust"

Approach  

The approach is to sort the array of input strings (conventional sorting of strings occur in lexicographical order), in this way, we will obtain lexicographic-ally smallest and largest strings at the left and right end of the string array. It is now evident that that longest prefix common to all the strings in the array will be the longest prefix common to first (lexicographically smallest) and last (lexicographically largest) strings of the now sorted array. We process the these two strings, evaluate the largest common prefix and simply return it.

Algorithm For Longest Common Prefix using Sorting  

  1. define base cases (n = 0,1).
  2. if size of string array is 0, the return empty string.
  3. if size of string array is 1, return the only string in it as the answer(prefix string).
  4. Sort the array of strings in lexicographical order.
  5. Take the first and last string of the string array.
  6. Find the longest common prefix among both the strings.
  7. return this prefix as the final answer.
See also
Best Time to Buy and Sell Stock III Leetcode Solution

Longest Common Prefix using SortingPin

C++ Program  

#include<bits/stdc++.h> 
using namespace std; 

// function to return the longest common prefix from the array of strings 
string longestCommonPrefix(string arr[], int n) 
{ 
  // If size is 0, return empty string 
    if (n == 0) 
        return ""; 
        
    // if only one string is present in the array
    // it itself is the prefix
    if (n == 1) 
        return arr[0]; 
  
    // Sort the array of strings 
    sort(arr, arr + n); 
    
    // first string of the array has minimum length
    int min = arr[0].length();
    
    // common prefix of the whole array
    // is common prefix of first and last strings
    string first = arr[0], last = arr[n - 1]; 
    
    // recur until strings have common characters
    int i = 0; 
    while (i < min && first[i] == last[i]) 
        i++; 
  
    string prefix = first.substr(0, i); 
    return prefix;
} 

// main program to implement above functions 
int main() 
{ 
  string arr[] = {"tutorialcup", "tutorial", "tussle", "tumble"}; 
  int n = sizeof (arr) / sizeof (arr[0]); 

  string ans = longestCommonPrefix(arr, n); 

  if (ans.length()) 
    cout << "Longest common prefix = "<< ans; 
  else
    cout << "no common prefix found";
    
  return 0; 
}
Longest common prefix = tu

Java Program For Longest Common Prefix using Sorting  

import java.io.*;
import java.util.*;
class tutorialcup 
{
   
    // function to return the longest common prefix from the array of strings 
    static String longestCommonPrefix(String arr[], int n) 
    {
    	// If size is 0, return empty string 
        if (n == 0) 
            return ""; 
            
        // if only one string is present in the array
        // it itself is the prefix
        if (n == 1) 
            return arr[0]; 
      
        // Sort the array of strings 
        Arrays.sort(arr);
        
        // first string of the array has minimum length
        int min = arr[0].length();
        
        // common prefix of the whole array
        // is common prefix of first and last strings
        String first = arr[0], last = arr[n - 1]; 
        
        // recur until strings have common characters
        int i = 0; 
        while (i < min && first.charAt(i) == last.charAt(i)) 
            i++; 
      
        String prefix = first.substring(0, i); 
        return prefix;
    } 

    // main program to implement above functions 
  public static void main (String[] args) 
  {
      String arr[] = {"tutorialcup", "tutorial", "tussle", "tumble"}; 
    	int n = arr.length; 
    
    	String ans = longestCommonPrefix(arr, n); 
    	if (ans.length() != 0) 
    		System.out.println("Longest common prefix = "+ans); 
    	else
    		System.out.println("no common prefix found");
  }
}
Longest common prefix = tu

Complexity Analysis  

  1. Time complexity : T(n) = O(n*m*logm)
  2. Space Complexity : A(n) = O(n)
See also
Reverse a String

n = length of the longest string

Please click Like if you loved this article?

m = number of strings in the string array.

References

Please click Like if you loved this article?