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.

Motivation to Learn Algorithms

Solve Leetcode Problems and Get Offers From Your Dream Companies | by Nil Madhab | LeetCode Simplified | Medium

Nil Madhab ・ Feb 6, 2021 ・

Medium

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.

Code in Java:

Code in C++:

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.

Thank You for reading and Follow this publication for more Leetcode Solutions!😃