You may have heard of prefixes in your school!
It is defined as an affix that is generally attached before a word or a phrase. As in a prefix of preview is ‘pre’ and of disappear is ‘dis’.
Well, in the coding universe prefixes also play a crucial role!
A useful and a much popular topic that is often asked from tech aspirants is the longest common prefix.
Among the given array of strings, you may need to find its longest common prefix.
The questions can be elaborative and may involve certain approaches that you need to follow to solve the problem statement.
Therefore, this tutorial would be of great help to you.
Read this blog till the end to equip yourself with the right knowledge!
How to find the longest common prefix?
Consider this problem statement in order to find the largest common prefix.
The given array of the strings S is given to you. Find its longest string i.e S which would be a prefix of certain other strings in a given array.
The Longest common prefix or LCP involves the pair of two strings which are S1 and S2 with the longest given string S that has the prefix for both the S1 and S2.
Take an example; the longest common prefix for the given ‘abcdefgh’ and ‘abcefgh’ would be ABC.
Approaches to follow
Horizontal Scanning Approach
The key idea behind this approach would be to horizontally scam all the array-related characters in a way so that you can easily find the given longest common prefix of all of them.
The simplest approach to find the longest prefix would be to get the set of strings which are LCP [S1 to Sn] to get the right observation.
You can obtain the LSP as:
LCP [ S1 …….SN] = LCP [ LCP ( LCP ( S1 S2)] , S3]…….SN]
The algorithm would be:
- Iterate from a string starting from the S1 till the SN
- With each of the iteration till your ith index, LCP [S1…Si] would be taken
- In this case, use the LCP with a given empty string for terminating the loop and returning the empty string
- Or, else, you can continue after you scan the N strings, LCP [S1, S2 ] will be obtained
Vertical Scanning Approach
The key idea behind this approach would be to scan or compare all the required characters from the top till bottom of an ith index of all the strings. In the cases, when all the LCP is considered quite small, this approach would be ideal to use. Here, you are not required to perform any given k number of comparisons.
Imagine a short string in a common array prefix. You can do the s number of comparisons in this case. One better way to optimise this would be to do a vertical type of scanning. You can compare all the related characters from the top to the bottom in a same column with the same character indexes. After that, you can move on towards a string.
- Iterate over a strong starting from the S1 to SN
- Then start by comparing a 0th index to its 1st index till the ith index for each given string
- In any case, the given ith index may don’t allow the matching of the characters, in this case you can terminate the algorithm to return the LPS ie 1 and i
- Otherwise, you can continue even after you scan the given N strings with the given LCP [ S1…..SN] which you can easily obtain
Divide and Conquer Approach
In this approach, you may need to divide a given string’s arrays in various subproblems in a way to merge them in order to get all the given LCP [ S1 …..SN]
Firstly, in this case, there may be a need for you to divide a given array in two parts. In turn, you can divide it from the left or the right array that will be obtained recursively by keeping on dividing the array until it gets divided further.
Time complexity in this case would be O[K] where the k represents the varied sum of characters in the given strings. The space complexity in this case would be the log N type recursive calls as each of them will occupy the space M.
Binary Search Approach
This is another useful approach which uses the topic of a binary tree to find the longest common prefix.
The algorithm in this case would be:
- Consider all the strings that have the given smallest length. And, let its given length will be L
- Then, consider any low variable with value 0 and the high would be L -1
- You can perform the binary search by dividing all strings in two halves which would be low-mid or the mid + 1 till high. You can also compare the substrings till the middle of a smallest string with all the left strings at their indexes. If its substring from the given 0 till mid is -1 which is common for all the substris, you can update its low with the mid +1 or update the high with the mid.
- If the given low == high, you can terminate all the algorithms and return a substring from the value 0 till mid
The time complexity in this case would be O [k, logN) in which the k in this case would be the given sum of certain characters of all the given strings.
The space complexity in this case would be O 
Additional Learning – Distinct characters
Another useful coding concept that is often asked from the candidates in a coding interview is of distinct characters. Distinct or non-repeating characters are the ones that may not get repeated in a given string. So, to get it right you can follow any apt approach for your given string of characters.
The longest common prefix is quite an essential coding topic that is often asked of the candidates of a coding interview. To get it right, follow the appropriate approaches mentioned in this blog and ace at this coding concept.
Learn well and pass your coding interview with flying colours!