Longest Common Prefix Problem Statement

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 <= 10⁵
• 1 <= number of queries <= 10⁵
• 1 <= total number of characters in the dictionary <= 10⁶
• 1 <= total number of characters in all queries <= 10⁶
• '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 it 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<String> longest_prefix(ArrayList<String> words, ArrayList<String> queries){
        ArrayList<String> 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

• 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 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

    /*
    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<String> longest_prefix(ArrayList<String> words, ArrayList<String> queries) {
        ArrayList<String> 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 longest common prefix problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

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, and career coaching to help you nail your next tech interview.

We offer 18 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:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.