## DEV Community is a community of 617,845 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Solve Leetcode Problems and Get Offers From Your Dream Companies | Problem 14. Longest Common Prefix (Easy)

LeetCode 14 | Longest Common Prefix (Easy)

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.

## 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.

## Let's get Started

### What is Prefix

A prefix of a string 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 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.

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.

## 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 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.