Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
4.
Dry run
5.
Code
6.
Complexity analysis
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

Longest Common Prefix using Divide and Conquer Algorithm

Author Malay Gain
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Common prefix between two strings means common substring starting with the beginning character of each given string. For example, the common prefix between ‘coding’ and ‘codingninjas’ is ‘coding’. Finding the longest common prefix is a very popular problem commonly asked in the interviews of top product-based companies.

This problem can be solved by various approaches, but here we will be only focusing on the divide and conquer approach.

 

Problem statement

You are given an array of strings. You need to find the longest common prefix among the given strings.

 

Input

arr[ ]={"coding","codingNinjas","codingSkill","codingEra"}

 

Output

          coding

 

Explanation

coding is the common prefix part among the given strings. We can’t find any longer common prefix. So, it is the longest common prefix. 

 

Note: Please try to solve the problem first and then see the solution below.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

In the divide and conquer approach; first, we need to divide the problem into subproblems and use the result of the subproblems for calculating the final result. 

 

  • Here we will divide the given array of strings into two halves.
  • Then repeat the possess on these halves, considering them as subproblems.
  • Then use the resulting strings of these subproblems to find the longest common prefix. 

 

string longestCommonPrefix(string arr[],int low_idx,int high_idx)
{
string ans;
if (low_idx == high_idx)
{
    return (arr[high_idx]);
}
       
 
if (high_idx > low_idx)
{
       
      int mid = low_idx + (high_idx - low_idx) / 2;

      //conquering for subproblems

      string s1 = longestCommonPrefix(arr, low_idx, mid);
      string s2 = longestCommonPrefix(arr, mid+1, high_idx);

      //common prefix between s1 and s2 
      //; using the result of subproblems for finding final ans
      string ans=commonPrefix(s1, s2);// longest common prefix
      return ans;
}
}

 

Dry run

 

Code

 

//C++ code for finding the longest common prefix

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

// function to find common prefix between two strings
string commonPrefix(string s1,string s2)
{
string commonPfix="";

int n1=s1.length();
int n2=s2.length();

for(int i=0,j=0;i<n1 &&j<n2;i++,j++)
{
if(s1[i]!=s2[j])
{
break;
}

//commonPfix.push_back(s1[i]);

commonPfix=commonPfix + s1[i];
}

return commonPfix;
}

//finctuon to find longest common prefix using divide and conquer approach
string longestCommonPrefix(string arr[],int low_idx,int high_idx)
{
string ans;
if (low_idx == high_idx)
{
    return (arr[high_idx]);
}
       
 
if (high_idx > low_idx)
{
       
      int mid = low_idx + (high_idx - low_idx) / 2;

      //conquering for subproblems

      string s1 = longestCommonPrefix(arr, low_idx, mid);
      string s2 = longestCommonPrefix(arr, mid+1, high_idx);

      //common prefix between s1 and s2 
      //; using the result of subproblems for finding final ans
      string ans=commonPrefix(s1, s2);// longest common prefix
      return ans;
}
}

//driver code

int main()
{
string arr[4]={"coding","codingNinjas","codingSkill","codingEra"};

cout<<"Longest common prefix is : "<<longestCommonPrefix(arr,0,3);
}

 

Output

 

Longest common prefix is : coding

 

Complexity analysis

The worst-case time complexity of the above algorithm is O(n*m), where n is the number of strings in the given array and m is the length of the longest string.

 

Space complexity is O(m*logn) as we need to store the longest common prefix of each subproblem.

Also check out - Substr C++, and Euclid GCD Algorithm

FAQs

  1. What is the divide and conquer algorithm?
    The process of dividing a problem recursively into two or more sub-problems of the same or related type until it can be solved directly.
     
  2. Application of divide and conquer algorithm?
    This algorithm is used to efficiently implement other algorithms such as quick sort or merge sort.

 

Key Takeaways

This article covered how to find the longest Common Prefix using the Divide and Conquer Algorithm.

 

If you want to practice such problems to get a good grasp on such concepts, then you can visit our Coding Ninjas Studio and also explore various topics like DSA, Web Technologies, Programing Fundamentals, Aptitude, and much more from our CN Library | Free Online Coding Resources.

 

 

Happy learning!

 

 

Previous article
Median of Two Sorted Arrays
Next article
Check if a Substring Exists, having Only Two Distinct Characters with The Frequency of One as Twice The Others
Live masterclass