About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Longest Common Prefix (LCP)

Longest Common Prefix 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.

Solution for Longest Common Prefix Problem

Watch this video by Omkar Deshpande, Director of Curriculum at Interview Kickstart and former Principal Engineer at Kosmix (now Walmart Labs), where he explains how to crack the Longest Common Prefix problem:

Read on for another variation of the Longest Common Prefix problem and two solutions.

Longest Common Prefix Problem Statement (Variation)

Given a dictionary of words, for each query string find the longest common prefix between the query and any dictionary word.

Example


{
"words": ["aab", "acd"],
"queries": ["aaz", "xyz", "acd"]
}

Output:


["aa", "", "acd"]

For every query we are looking for the longest among the common prefixes with dictionary words (not a common prefix with all the dictionary words). Let us consider each query separately:

  1. "aaz" has a common prefix of "aa" with the first dictionary word and "a" with the second one. "aa" is the longest of the two so that's the answer.
  2. "xyz" has no (empty string) common prefixes with any of the dictionary words, so "" is the answer.
  3. "acd" has common prefixes of "a" and "acd" with the two dictionary words. "acd" is longer so it becomes the answer.

Notes

Constraints:

  • 1 <= number of words in the dictionary <= 105
  • 1 <= number of queries <= 105
  • 1 <= total number of characters in the dictionary <= 106
  • 1 <= total number of characters in all queries <= 106
  • 'a' <= character in a word or in a query <= 'z'
  • Each word and each query is at least one character long

We have provided two solutions. We will refer to the size of words array as n, size of queries array as q and the maximum length of a string present among both these arrays as l.

Longest Common Prefix Solution 1: Brute Force

  • We are given n strings in the array words and q strings in the array queries.
  • For each query we iterate over all the n words and for each of these words, we find the longest common prefix between the query and the word. We always keep track of the longest one found.
  • We add the longest prefix found to the answer array and move on to the next query.
  • When we are done with all queries, the answer array can be returned.

Time Complexity

O(n * q * l): Here, we simply traverse the array queries and for each element of this array, we try to find the matching prefix for every string of array words. Hence, the complexity turns out to be O(n * q * l).

Auxiliary Space Used

O(l): For every string, we simply store the maximum prefix that can match any of the strings present in array words.

Space Complexity

O(n * l + q * l)

Space used for input: O(n * l + q * l)

Auxiliary space used: O(l)

Space used for output: O(q * l)

Hence, total space complexity: O(n * l + q * l)

Code for Longest Common Prefix Solution 1: Brute Force


/*

   Asymptotic complexity in terms of size of `words` `n`, size of `queries` `q`


   and maximum length of a string present in `words` or `queries` `l`:


   * Time: O(n * q * l).


   * Auxiliary space: O(l).


   * Total space: O(n * l + q * l).


   */


   public static ArrayList longest_prefix(ArrayList words, ArrayList queries){


       ArrayList ans = new ArrayList<>();


       //loop through all the queries


       for(String s : queries){


           String answer = "";


           //loop through all the words


           for(String t : words){


               StringBuilder sb = new StringBuilder();


               //we keep on checking until we find a prefix


               for(int i = 0; i < s.length() && i < t.length(); i++){


                   if(s.charAt(i) == t.charAt(i)){


                       sb.append(s.charAt(i));


                   }


                   else{


                       break;


                   }


               }


               if(sb.length() > answer.length()){


                   answer = sb.toString();


               }


           }


           ans.add(answer);


       }


       return ans;


   }

Longest Common Prefix Solution 2: Optimal Solution

  • We are given n strings in the array words and q strings in the array queries.
  • Before answering any query, we create a Trie and add all n strings present in the array words to it.
  • Now, for each string present in the query, we check for the maximum possible prefix match in the trie. We modify the search method of a trie to return the maximum prefix.
  • Finally, after processing all the strings present in array queries and adding the maximum prefixed for each to the answer array, we return the answer array.

Time Complexity

O(n * l + q * l): Insertion in a trie takes time equal to the length of the string, that is O(l), so inserting n strings take O(n * l) time. Similarly, finding the maximum prefix takes O(l) time. So for q queries, it takes O(n * l) time. Hence time complexity turns out to be O(n * l + q * l).

Auxiliary Space Used

O(l * n): We are inserting all n strings present in array words in Trie, so in the worst case, it would take O(n * l * 26) space.

Space Complexity

O(n * l + q * l)

Space used for input: O(n * l + q * l)

Auxiliary space used: O(n * l)

Space used for output: O(q * l)

Hence, total space complexity: O(n * l + q * l)

Code for Longest Common Prefix Solution 2: Optimal Solution


/*




   Asymptotic complexity in terms of size of `words` `n`, size of `queries` `q`


   and maximum length of a string present in `words` or `queries` `l`:


   * Time: O(n * l + q * l).


   * Auxiliary space: O(l * n).


   * Total space: O(n * l + q * l).


   */


   public static ArrayList longest_prefix(ArrayList words, ArrayList queries) {


       ArrayList ans = new ArrayList<>();


       Trie trie = new Trie();


       //insert all the words in the trie


       for (String s : words) {


           trie.insert(s);


       }


       //find answers for all the queries


       for (String s : queries) {


           String answer = trie.maxPrefix(s);


           ans.add(answer);


       }


       return ans;


   }







   //A trieNode which holds 26 nodes


   static class TrieNode {


       TrieNode[] nodes = new TrieNode[26];


       TrieNode() {


           for (int i = 0; i < 26; i++) {


               nodes[i] = null;


           }


       }


   }







   static class Trie {


       TrieNode head = new TrieNode();


       //insert a string in the trie


       public void insert(String s) {


           TrieNode temp = head;


           /*for every character, we see if there is a node for it in trie.


            * if there isn't a node, we create a new one.


            */


           for (char ch : s.toCharArray()) {


               TrieNode check = temp.nodes[ch - 'a'];


               if (check != null) {


                   temp = check;


               } else {


                   temp = temp.nodes[ch - 'a'] = new TrieNode();


               }


           }


       }







       //find the maximum prefix for a string s from the trie


       public String maxPrefix(String s) {


           TrieNode temp = head;


           StringBuilder sb = new StringBuilder();


           /*finds the prefix until there is a node for that character,


            * other wise breaks the loop.


            */


           for (char ch : s.toCharArray()) {


               TrieNode check = temp.nodes[ch - 'a'];


               if (check == null) {


                   break;


               }


               temp = check;


               sb.append(ch);


           }


           return sb.toString();


       }


   }

We hope that these solutions to the Longest Common Prefix (LCP) problem for an array of strings will help you level up your coding skills. Companies such as Google include Longest Common Prefix interview questions in their tech interviews. 

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE Webinar to understand the best way to prepare. 

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview. 

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

To learn more, register for the FREE Webinar.

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Recommended Posts

All Posts