Longest Common Prefix

Moderate
0/80
Average time to solve is 40m
129 upvotes
Asked in companies
AdobeGrofersDunzo

Problem statement

You are given an array ‘ARR’ consisting of ‘N’ strings. Your task is to find the longest common prefix among all these strings. If there is no common prefix, you have to return an empty string.

A prefix of a string can be defined as a substring obtained after removing some or all characters from the end of the string.

For Example: 
Consider ARR = [“coding”, ”codezen”, ”codingninja”, ”coders”]
The longest common prefix among all the given strings is “cod” as it is present as a prefix in all strings. Hence, the answer is “cod”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains a single integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of strings in the array.

The next line contains ‘N’ space-separated strings denoting the elements of the array ‘ARR’.
Output Format: 
For each test case, print a single string corresponding to the longest common prefix.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 3000
1 <= |ARR[i]| <=1000

Each string consists of only lowercase letters.

Time limit: 1 sec
Sample Input 1:
2
4
coding codezen codingninja coder
3
night ninja nil
Sample Output 1:
cod
ni
Explanation of sample input 1:
For the first test case, 
The longest common prefix among all the given strings is “cod” as it is present as a prefix in all strings. Hence, the answer is “cod”.

For the second test case,
The longest common prefix among all the given strings is “ni” as it is present as a prefix in all strings. Hence, the answer is “ni”.
Sample Input 2:
2
3
applejuice applepie apple
4
car cus cart carat
Sample Output 2:
apple
c
Hint

Try to find the optimal condition to include the character in the longest common prefix.

Approaches (4)
Iterative Scanning

In this approach, we will iterate through each character of the first string and check if the same character exists in each string or not. We will maintain a variable longestPrefix to store the longest common prefix.

 

We will traverse idx from 0 to the length of ARR[0] -1.

  1. We will iterate index from 1 to N-1 and check if ARR[index][idx] is equal to ARR[0][idx].
  2. If the condition is true for all strings, we can add ARR[0][idx] in the common prefix string, and we will insert ARR[0][idx] in longestPrefix. Otherwise, the search is completed for the longest common prefix.

In the end, we will return the variable longestPrefix.

 

Algorithm:

  • We will declare a string longestPrefix to store the longest prefix string of all strings.
  • We will iterate through the first string of ARR and check each of its characters is present in all other strings or not.
  • Iterate idx from 0 to length of ARR[0] - 1 ,do the following:
    • Set ch as ARR[0][idx]. The variable ch stores the character to be searched.
    • Set matched as true. The variable stores if it is possible to insert ch into the longestPrefix.
    • We will iterate index from 1 to N-1, do the following:
      • Check if the length of ARR[index] is less than or equal to the variable idx or ARR[index][idx] is not equal to ch.
        • Set matched as false.
        • Break this loop.
    • If matched is true, we can insert character ch into longestPrefix. Otherwise, break this loop as the longest common prefix is already found.
  • Return the string longestPrefix corresponding to the longest prefix string of all the strings in the given array.
Time Complexity

O(N*M), where N is the number of strings in the array and M is the shortest length of the string present in the array.

 

We are doing M iteration, and in each iteration, we are traversing through the strings that take O(N) time. Hence, the overall time complexity is O(N*M).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Longest Common Prefix
Full screen
Console