Solve Leetcode Problems and Get Offers From Your Dream Companies | Problem 14.  Longest Common Prefix (Easy)
Tags: algorithms, programming, codenewbie
Published: 2021-01-26 17:14:20

LeetCode 14 | Longest Common Prefix (Easy)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/9yscc1og4e6llzg2msvg.jpg)
In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem Problem 1429. First Unique Number.

A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
## Motivation to Learn Algorithms
{% medium https://medium.com/leetcode-simplified/solve-leetcode-problems-and-get-offers-from-your-dream-companies-2786415be0b7 %}
## Problem Statement

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string.
### Sample Input

**Example 1:**

`Input: strs = ["flower","flow","flight"]
Output: "fl" `

**Example 2:**

`Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.`

**Constraints**

* `0 <= strs.length <= 200`
* `0 <= strs[i].length <= 200`
* `strs[i]` consists of only lower-case English letters.

You can find the problem [here](https://leetcode.com/problems/longest-common-prefix/).
## Let's get Started
### What is Prefix

A prefix of a [string](https://medium.com/javarevisited/top-21-string-programming-interview-questions-for-beginners-and-experienced-developers-56037048de45) is any substring that starts from the first character. The number of different prefixes of a string is equal to its length. For example, the string “flower” will have 6 different prefixes:

`f
fl
flo
flow
flowe
flower`

In the problem statement, we are given an array of strings. We have to return the longest string which occurs as a prefix in all our strings.
**Observation**

Is there any upper limit on the length of our answer string?

Yes. As said earlier, the number of different prefixes of a string is equal to its length. So the maximum possible length of the common prefix for a group of strings is equal to the length of the smallest string.

`flower
flow
flowchartIn this the upper limit on LCP length is 4, and the length of answer is also 4
Answer = flow`

Remember, the upper limit does not mean the length of our answer always!

`flower
flow
flagIn this the upper limit on LCP length is 4, but the length of answer is 2
Answer = fl`

**Solution**

Let `minLen` be the length of the smallest string. So from our observation, we can conclude that while finding the [LCP](https://javarevisited.blogspot.com/2016/07/how-to-calculate-gcf-and-lcm-of-two-numbers-in-java-example.html#axzz6kGEVKsf7) we have to only consider the first `minLen` characters of every string.

In the beginning, we may assume that all the strings do not share any common prefix. So our `ans` variable will store an empty string. Then we will gradually expand our answer character by character. We will loop from the index `0` to `minLen-1`. If all the strings have the same character at a given index, this means this character is a part of our LCP. We will append this character to our answer. But if we find an index `i` at which all the strings do not share a common character, we will stop the process. After this, our answer string will not expand any further.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/g0x4an0gjpd6w8ssc3f9.png)
In the above example, our `minLen` is 4. The character at the first two indexes are the same across all the strings, so they are part of our answer. The third character is not the same across all the strings, hence we stop our process and return the answer.
## Code in Java:
{% gist https://gist.github.com/ChitreshApte/ffe93650b03c640a4857d06ff15ead43.js %}
## Code in C++:
{% gist https://gist.github.com/ChitreshApte/8b2a3eee87f4d20aed17c9844d805910.js %}
## Time and Space Complexity

The time complexity of our solution is O(n*m), where n is the size of `strs` array and `m` is the length of the [longest string](https://medium.com/hackernoon/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0) in our array. In the worst case, we may have to check every character of all the strings. For example, we may have an array in which all the strings are equal.

The space complexity of our solution is O(1). Apart from the function argument(input) and our answer variable, we are only using some constant space that is independent of our input size.
**Practice Makes Perfect**

Can this problem be solved using a Trie data structure? Think about it.
### Thank You for reading and Follow this publication for more Leetcode Solutions!😃