'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Last Updated: 24 Jul, 2021

Longest Common Prefix

Moderate
Asked in companies
CiscoAdobeShareChat

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

Approaches

01 Approach

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.