# Longest Common Prefix using Sorting

Difficulty Level Easy
StringViews 1987

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.

## 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)

n = length of the longest string

m = number of strings in the string array.

References

Translate »