Given an array, arr[] of "n" different strings, the task is to find the longest common prefix among all strings present in the array.

Input: **{"cup", "cupboard", "cut", "curse"}**, Output: **"cu"**

Input:** {"hit", "duper", "super"}**, Output: **"-1"**

## Solutions

### Method 1: In O(n * length of prefix) time and O(1) space

The idea is to first calculate the **length of shortest string**, because the common prefix can not exceed the length of shortest string.

Next, start a loop from **"0" to "length of shortest string"**, and in each iteration check if the **i ^{th}** character is same in each string.

If **i ^{th}** character is same in each string, than this character will be part of common prefix.

Else if in any iteration the **i ^{th}** character is different for any string, return substring of any string from

**0 to i.**

##### Complexity

The time complexity of this solution is **O(n * length of prefix)** and space complexity is** O(N)**.