# Longest common prefix using divide and conquer algorithm

Divide and Conquer is a widely used algorithmic paradigm that breaks down a problem into subproblems, solves them independently, and combines the solutions to solve the original problem. In this article, we will explore the Divide and Conquer approach to find the Longest Common Prefix (LCP) among a set of strings.

## Problem Statement

Given an array of strings, we want to find the longest common prefix that is shared by all the strings. For example, if the input array is ["cool", "coder", "confirm", "cow"], the longest common prefix is "co".

## Pseudocode Algorithm

``````String commonPrefix(String s1, String s2):
result = ""
i = 0
n = min(s1.length(), s2.length())
while i < n and s1.charAt(i) == s2.charAt(i):
result = result + s1.charAt(i)
i = i + 1
return result

String longestCommonPrefix(String arr[], int start, int end):
if start == end:
return arr[start]
if start > end:
return ""
mid = start + (end - start) / 2
s1 = longestCommonPrefix(arr, start, mid)
s2 = longestCommonPrefix(arr, mid + 1, end)
return commonPrefix(s1, s2)``````

The algorithm consists of two main functions:

• `commonPrefix`: This function finds the common prefix between two strings `s1` and `s2`. It iterates through the characters of the strings until it finds a mismatch or reaches the end of the shorter string.
• `longestCommonPrefix`: This function recursively divides the input array into two halves until there is only one string left. It then combines the common prefixes of the left and right halves using the `commonPrefix` function.

## Code Solution

``````/*
Java program for
Longest common prefix using divide and conquer algorithm
*/
public class Prefix
{
// Returns the common prefix of two string
String commonPrefix(String s1,String s2)
{
String result = "";

int i = 0;

int n = s1.length();

if(s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while(i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i);
i++;
}

return result;

}
String longestCommonPrefix(String arr[], int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if(start > ends)
{

return "";
}

// Get middle of subarray
int mid = start + (ends - start) / 2;

String s1 = longestCommonPrefix(arr, start, mid);
String s2 = longestCommonPrefix(arr, mid+1, ends);
// Return common of s1 and s2
return commonPrefix(s1, s2);

}
public static void main(String[] args)
{

String []arr = {"cool", "coder", "confirm", "cow"};

int n = arr.length;

System.out.print(" Longest Common Prefix is : "+ans);
}
}``````

#### Output

`` Longest Common Prefix is : co``
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
public:
// Returns the common prefix of two string
string commonPrefix(string s1, string s2)
{
string result = "";
int i = 0;
int n = s1.length();
if (s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while (i < n && s1[i] == s2[i])
{
result = result  +  s1[i];
i++;
}
return result;
}
string longestCommonPrefix(string arr[], int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
int mid = start + (ends - start) / 2;
string s1 = this->longestCommonPrefix(arr, start, mid);
string s2 = this->longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this->commonPrefix(s1, s2);
}
};
int main()
{
string arr[] = {
"cool" , "coder" , "confirm" , "cow"
};
int n = sizeof(arr) / sizeof(arr);
string ans = task->longestCommonPrefix(arr, 0, n - 1);
cout << " Longest Common Prefix is : " << ans;
return 0;
}``````

#### Output

`` Longest Common Prefix is : co``
``````// Include namespace system
using System;
/*
Csharp program for
Longest common prefix using divide and conquer algorithm
*/
public class Prefix
{
// Returns the common prefix of two string
String commonPrefix(String s1, String s2)
{
String result = "";
int i = 0;
int n = s1.Length;
if (s2.Length < n)
{
// Got s2 length because it is smaller to s1
n = s2.Length;
}
while (i < n && s1[i] == s2[i])
{
result = result + s1[i];
i++;
}
return result;
}
String longestCommonPrefix(String[] arr, int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
int mid = start + (ends - start) / 2;
String s1 = this.longestCommonPrefix(arr, start, mid);
String s2 = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
public static void Main(String[] args)
{
String[] arr = {
"cool" , "coder" , "confirm" , "cow"
};
int n = arr.Length;
String ans = task.longestCommonPrefix(arr, 0, n - 1);
Console.Write(" Longest Common Prefix is : " + ans);
}
}``````

#### Output

`` Longest Common Prefix is : co``
``````package main

import "fmt"
/*
Go program for
Longest common prefix using divide and conquer algorithm
*/

// Returns the common prefix of two string
func commonPrefix(s1, s2 string) string {
var result string = ""
var i int = 0
var n int = len(s1)
if len(s2) < n {
// Got s2 length because it is smaller to s1
n = len(s2)
}
for (i < n && s1[i] == s2[i]) {
result = result +string(s1[i])
i++
}
return result
}
func longestCommonPrefix(arr[] string, start int, ends int) string {
if start == ends {
return (arr[start])
}
if start > ends {
return ""
}
// Get middle of subarray
var mid int = start + (ends - start) / 2
var s1 string = longestCommonPrefix(arr, start, mid)
var s2 string = longestCommonPrefix(arr, mid + 1, ends)
// Return common of s1 and s2
return commonPrefix(s1, s2)
}
func main() {

var arr = [] string {"cool","coder","confirm","cow"}
var n int = len(arr)
var ans string = longestCommonPrefix(arr, 0, n - 1)
fmt.Print(" Longest Common Prefix is : ", ans)
}``````

#### Output

`` Longest Common Prefix is : co``
``````<?php
/*
Php program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
function commonPrefix(\$s1, \$s2)
{
\$result = "";
\$i = 0;
\$n = strlen(\$s1);
if (strlen(\$s2) < \$n)
{
// Got s2 length because it is smaller to s1
\$n = strlen(\$s2);
}
while (\$i < \$n && \$s1[\$i] == \$s2[\$i])
{
\$result = \$result.strval(\$s1[\$i]);
\$i++;
}
return \$result;
}

function longestCommonPrefix(\$arr, \$start, \$ends)
{
if (\$start == \$ends)
{
return (\$arr[\$start]);
}
if (\$start > \$ends)
{
return "";
}
// Get middle of subarray
\$mid = \$start + (int)((\$ends - \$start) / 2);
\$s1 = \$this->longestCommonPrefix(\$arr, \$start, \$mid);
\$s2 = \$this->longestCommonPrefix(\$arr, \$mid + 1, \$ends);
// Return common of s1 and s2
return \$this->commonPrefix(\$s1, \$s2);
}
}

function main()
{
\$arr = array("cool", "coder", "confirm", "cow");
\$n = count(\$arr);
\$ans = \$task->longestCommonPrefix(\$arr, 0, \$n - 1);
echo(" Longest Common Prefix is : ".\$ans);
}
main();``````

#### Output

`` Longest Common Prefix is : co``
``````/*
Node JS program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
commonPrefix(s1, s2)
{
var result = "";
var i = 0;
var n = s1.length;
if (s2.length < n)
{
// Got s2 length because it is smaller to s1
n = s2.length;
}
while (i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i);
i++;
}
return result;
}
longestCommonPrefix(arr, start, ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
var mid = start + parseInt((ends - start) / 2);
var s1 = this.longestCommonPrefix(arr, start, mid);
var s2 = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
}

function main()
{
var arr = ["cool", "coder", "confirm", "cow"];
var n = arr.length;
var ans = task.longestCommonPrefix(arr, 0, n - 1);
process.stdout.write(" Longest Common Prefix is : " + ans);
}
main();``````

#### Output

`` Longest Common Prefix is : co``
``````#    Python 3 program for
#    Longest common prefix using divide and conquer algorithm
class Prefix :
#  Returns the common prefix of two string
def commonPrefix(self, s1, s2) :
result = ""
i = 0
n = len(s1)
if (len(s2) < n) :
#  Got s2 length because it is smaller to s1
n = len(s2)

while (i < n and s1[i] == s2[i]) :
result = result + str(s1[i])
i += 1

return result

def longestCommonPrefix(self, arr, start, ends) :
if (start == ends) :
return (arr[start])

if (start > ends) :
return ""

#  Get middle of sublist
mid = start + int((ends - start) / 2)
s1 = self.longestCommonPrefix(arr, start, mid)
s2 = self.longestCommonPrefix(arr, mid + 1, ends)
#  Return common of s1 and s2
return self.commonPrefix(s1, s2)

def main() :
arr = ["cool", "coder", "confirm", "cow"]
n = len(arr)
ans = task.longestCommonPrefix(arr, 0, n - 1)
print(" Longest Common Prefix is : ", ans, end = "")

if __name__ == "__main__": main()``````

#### Output

`` Longest Common Prefix is :  co``
``````#    Ruby program for
#    Longest common prefix using divide and conquer algorithm
class Prefix
#  Returns the common prefix of two string
def commonPrefix(s1, s2)
result = ""
i = 0
n = s1.length
if (s2.length < n)
#  Got s2 length because it is smaller to s1
n = s2.length
end

while (i < n && s1[i] == s2[i])
result = result + s1[i].to_s
i += 1
end

return result
end

def longestCommonPrefix(arr, start, ends)
if (start == ends)
return (arr[start])
end

if (start > ends)
return ""
end

#  Get middle of subarray
mid = start + (ends - start) / 2
s1 = self.longestCommonPrefix(arr, start, mid)
s2 = self.longestCommonPrefix(arr, mid + 1, ends)
#  Return common of s1 and s2
return self.commonPrefix(s1, s2)
end

end

def main()
arr = ["cool", "coder", "confirm", "cow"]
n = arr.length
ans = task.longestCommonPrefix(arr, 0, n - 1)
print(" Longest Common Prefix is : ", ans)
end

main()``````

#### Output

`` Longest Common Prefix is : co``
``````/*
Scala program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix()
{
// Returns the common prefix of two string
def commonPrefix(s1: String, s2: String): String = {
var result: String = "";
var i: Int = 0;
var n: Int = s1.length();
if (s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while (i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i).toString();
i += 1;
}
return result;
}
def longestCommonPrefix(arr: Array[String], start: Int, ends: Int): String = {
if (start == ends)
{
return (arr(start));
}
if (start > ends)
{
return "";
}
// Get middle of subarray
var mid: Int = start + (ends - start) / 2;
var s1: String = longestCommonPrefix(arr, start, mid);
var s2: String = longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return commonPrefix(s1, s2);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Prefix = new Prefix();
var arr: Array[String] = Array("cool", "coder", "confirm", "cow");
var n: Int = arr.length;
var ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : " + ans);
}
}``````

#### Output

`` Longest Common Prefix is : co``
``````import Foundation;
/*
Swift 4 program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
func commonPrefix(_ s1: String, _ s2: String) -> String
{
var result: String = "";
var i: Int = 0;
var n: Int = s1.count;
let t1 = Array(s1);
let t2 = Array(s2);
if (s2.count < n)
{
// Got s2 length because it is smaller to s1
n = s2.count;
}
while (i < n && t1[i] == t2[i])
{
result = result + String(t1[i]);
i += 1;
}
return result;
}
func longestCommonPrefix(
_ arr: [String],
_ start: Int,
_ ends: Int) -> String
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
let mid: Int = start + (ends - start) / 2;
let s1: String = self.longestCommonPrefix(arr, start, mid);
let s2: String = self.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return self.commonPrefix(s1, s2);
}
}
func main()
{
let arr: [String] = ["cool", "coder", "confirm", "cow"];
let n: Int = arr.count;
let ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : ", ans, terminator: "");
}
main();``````

#### Output

`` Longest Common Prefix is :  co``
``````/*
Kotlin program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
fun commonPrefix(s1: String, s2: String): String
{
var result: String = "";
var i: Int = 0;
var n: Int = s1.length;
if (s2.length < n)
{
// Got s2 length because it is smaller to s1
n = s2.length;
}
while (i < n && s1.get(i) == s2.get(i))
{
result = result + s1.get(i).toString();
i += 1;
}
return result;
}
fun longestCommonPrefix(
arr: Array < String > , start: Int, ends: Int): String
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
val mid: Int = start + (ends - start) / 2;
val s1: String = this.longestCommonPrefix(arr, start, mid);
val s2: String = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < String > = arrayOf("cool", "coder", "confirm", "cow");
val n: Int = arr.count();
val ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : " + ans);
}``````

#### Output

`` Longest Common Prefix is : co``

## Explanation

Let's walk through the code to understand how it works:

1. We start by defining the `commonPrefix` function. It takes two strings, `s1` and `s2`, as input. We initialize an empty string called `result` to store the common prefix.
2. We compare the characters of `s1` and `s2` at each position. If they are equal, we append the character to `result` and increment the index `i`.
3. We continue this process until we reach the end of either string or find a mismatch.
4. The `commonPrefix` function returns the resulting string.
5. Next, we define the `longestCommonPrefix` function. It takes an array of strings, `arr`, and the start and end indices as input.
6. If the start and end indices are the same, we return the string at that index. This serves as the base case for the recursion.
7. If the start index is greater than the end index, it means we have an empty array, so we return an empty string.
8. We calculate the middle index, `mid`, and recursively call `longestCommonPrefix` on the left and right halves of the array.
9. We combine the common prefixes of the left and right halves using the `commonPrefix` function.
10. The resulting common prefix is returned as the output of the `longestCommonPrefix` function.

The main function creates an instance of the `Prefix` class and initializes an array of strings. It calls the `longestCommonPrefix` function with the array and the range of indices. Finally, it prints the resulting longest common prefix.

## Output Explanation

The output of the given code is "co". It correctly identifies the longest common prefix among the strings "cool", "coder", "confirm", and "cow".

## Time Complexity

The time complexity of this algorithm can be analyzed as follows:

• Let `n` be the number of strings in the input array, and let `m` be the length of the longest string.
• The `commonPrefix` function takes O(m) time to compare the characters of two strings.
• The `longestCommonPrefix` function recursively divides the input array into two halves until there is only one string left. This process takes O(log n) iterations.
• At each iteration, the `commonPrefix` function is called on two strings, which takes O(m) time.

Therefore, the overall time complexity of the algorithm is O(m * log n).

## Finally

In this article, we explored the Divide and Conquer approach to finding the Longest Common Prefix (LCP) among a set of strings. We discussed the problem statement, provided a detailed explanation of the pseudocode algorithm, and analyzed its time complexity. The code implementation in Java was also provided, along with an explanation of the output.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.