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 ・ ・
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 lowercase 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 minLen1
. 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.
Discussion (0)