Longest Common Prefix using Character by Character Matching

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.

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.

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

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.