Solution


Approach 1: Horizontal scanning

Intuition

For a start we will describe a simple way of finding the longest prefix shared by a set of strings . We will use the observation that :

Algorithm

To employ this idea, the algorithm iterates through the strings , finding at each iteration the longest common prefix of strings When is an empty string, the algorithm ends. Otherwise after iterations, the algorithm returns .

Finding the longest common prefix

Figure 1. Finding the longest common prefix (Horizontal scanning)

Complexity Analysis

  • Time complexity : , where S is the sum of all characters in all strings.

    In the worst case all strings are the same. The algorithm compares the string with the other strings There are character comparisons, where is the sum of all characters in the input array.

  • Space complexity : . We only used constant extra space.


Approach 2: Vertical scanning

Algorithm

Imagine a very short string is at the end of the array. The above approach will still do comparisons. One way to optimize this case is to do vertical scanning. We compare characters from top to bottom on the same column (same character index of the strings) before moving on to the next column.

Complexity Analysis

  • Time complexity : , where S is the sum of all characters in all strings. In the worst case there will be equal strings with length and the algorithm performs character comparisons. Even though the worst case is still the same as Approach 1, in the best case there are at most comparisons where is the length of the shortest string in the array.
  • Space complexity : . We only used constant extra space.


Approach 3: Divide and conquer

Intuition

The idea of the algorithm comes from the associative property of LCP operation. We notice that : , where is the longest common prefix in set of strings ,

Algorithm

To apply the observation above, we use divide and conquer technique, where we split the problem into two subproblems and , where mid is . We use their solutions lcpLeft and lcpRight to construct the solution of the main problem . To accomplish this we compare one by one the characters of lcpLeft and lcpRight till there is no character match. The found common prefix of lcpLeft and lcpRight is the solution of the .

Finding the longest common prefix

Figure 2. Finding the longest common prefix of strings using divide and conquer technique

Complexity Analysis

In the worst case we have equal strings with length

  • Time complexity : , where is the number of all characters in the array, Time complexity is . Therefore time complexity is . In the best case this algorithm performs comparisons, where is the shortest string of the array

  • Space complexity :

    There is a memory overhead since we store recursive calls in the execution stack. There are recursive calls, each store need space to store the result, so space complexity is



The idea is to apply binary search method to find the string with maximum value L, which is common prefix of all of the strings. The algorithm searches space is the interval , where minLen is minimum string length and the maximum possible common prefix. Each time search space is divided in two equal parts, one of them is discarded, because it is sure that it doesn't contain the solution. There are two possible cases: S[1...mid] is not a common string. This means that for each j > i S[1..j] is not a common string and we discard the second half of the search space. S[1...mid] is common string. This means that for for each i < j S[1..i] is a common string and we discard the first half of the search space, because we try to find longer common prefix.

Finding the longest common prefix

Figure 3. Finding the longest common prefix of strings using binary search technique

Complexity Analysis

In the worst case we have equal strings with length

  • Time complexity : , where is the sum of all characters in all strings.

    The algorithm makes iterations, for each of them there are comparisons, which gives in total time complexity.

  • Space complexity : . We only used constant extra space.


Further Thoughts / Follow up

Let's take a look at a slightly different problem:

Given a set of keys S = , find the longest common prefix among a string q and S. This LCP query will be called frequently.

We could optimize LCP queries by storing the set of keys S in a Trie. For more information about Trie, please see this article Implement a trie (Prefix trie). In a Trie, each node descending from the root represents a common prefix of some keys. But we need to find the longest common prefix of a string q and all key strings. This means that we have to find the deepest path from the root, which satisfies the following conditions: it is prefix of query string q each node along the path must contain only one child element. Otherwise the found path will not be a common prefix among all strings. * the path doesn't comprise of nodes which are marked as end of key. Otherwise the path couldn't be a prefix a of key which is shorter than itself.

Algorithm

The only question left, is how to find the deepest path in the Trie, that fulfills the requirements above. The most effective way is to build a trie from strings. Then find the prefix of query string q in the Trie. We traverse the Trie from the root, till it is impossible to continue the path in the Trie because one of the conditions above is not satisfied.

Finding the longest common prefix using Trie

Figure 4. Finding the longest common prefix of strings using Trie

Complexity Analysis

In the worst case query has length and it is equal to all strings of the array.

  • Time complexity : preprocessing , where is the number of all characters in the array, LCP query .

    Trie build has time complexity. To find the common prefix of in the Trie takes in the worst case .

  • Space complexity : . We only used additional extra space for the Trie.