Longest Common Prefix using Character by Character Matching  

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg eBay Facebook Google Microsoft VMware Yahoo
String

Problem Statement  

In the “Longest Common Prefix using Character by Character Matching” problem we have given an integer value N and N strings. Write a program to find the longest common prefix of the given strings.

Input Format  

The first line containing an integer value N which denotes the number of strings.

Next N lines containing a string.

Output Format  

The first and only one line containing a string “ans” which is our Longest Common Prefix of the given N strings. If no such prefix exist then print -1.

Please click Like if you loved this article?

Constraints  

  • 1<=|N|<=10^3
  • 1<=|s[i]|<=10^3 where i from 0 to N-1
  • s[i][j] must be a lower case English alphabet where i from 0 to N-1, and j from 0 to |s[i]|.

Example  

5
abcde 
abba 
abaa 
abbbbb 
ababab
ab

Explanation: Here we can see the common prefix of the 1st and second string is “ab”. Now check this prefix with every string one by one and get the final prefix which is “ab”.

Algorithm  

Here, instead of going through strings one by one, we will go through characters one by one.

1. We find the minimum length string from the input string array.
   a. Traverse the string array.
   b. Return the length of the minimum length string.

See also
Top K Frequent Words

2. We traverse all the strings, and compare characters at the same position.

3. If the current character is the same in all strings (same position) add it to the result.

4. Return final result.

Implementation  

C++ Program for Longest Common Prefix using Character by Character Matching

#include <bits/stdc++.h>
using namespace std;
 
string  common_prefix(vector<string> v)
{
    int n=v.size();
    int ml = v[0].length(); 
  for(int i=1;i<n;i++)
  {
      int temp = v[i].length();
    if(temp < ml)
    {
      ml=temp; 
    }
  }
  string ans=""; 
  char ch; 
  for (int i=0;i<ml;i++) 
  { 
    ch=v[0][i]; 
    for(int j=1;j<n;j++)
    {
      if(v[j][i]!=ch)
      {
        return ans; 
      }
    }
    ans+=ch; 
  } 
  return ans; 
}
 
int main()
{
    int n;
    cin>>n;
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        v.push_back(x);
    }
    string ans = common_prefix(v);
    if(ans.length())
    {
        cout<<ans<<endl;
    }
    else
    {
        cout<<-1<<endl;
    }
    return 0;
}

Java Program for Longest Common Prefix using Character by Character Matching

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String common_prefix(Vector<String> v)
    {
            int n=v.size();
            int ml = v.get(0).length(); 
                for(int i=1;i<n;i++)
                {
                    int temp = v.get(i).length();
                        if(temp < ml)
                        {
                                ml=temp; 
                        }
                }
                String ans=""; 
                char ch; 
                for (int i=0;i<ml;i++) 
                { 
                        ch=v.get(0).charAt(i); 
                        for(int j=1;j<n;j++)
                        {
                                if(v.get(j).charAt(i)!=ch)
                                {
                                        return ans; 
                                }
                        }
                        ans+=ch; 
                } 
                return ans; 
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        Vector<String> v = new Vector<String>(n+1);
        for(int i=0;i<n;i++)
        {
            String x = sr.next();
            v.add(x);
        }
        String ans = common_prefix(v);
        if(ans.length()!=0)
        {
            System.out.println(ans);
        }
        else
        {
            System.out.println("-1");
        }
    }
}




5
abcde 
abba 
abaa 
abbbbb 
ababab
ab

Complexity Analysis for Longest Common Prefix using Character by Character Matching  

Time Complexity

O(n*m) where n is the total number of strings and m is the length of the maximum string.

Space Complexity

O(m) where m is the length of the maximum string. We use this space to store the common prefix after performing an operation between two strings.

Please click Like if you loved this article?