Register for our webinar

### How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

# 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 <= 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 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:

‍To learn more, register for the FREE webinar.

### Try yourself in the Editor

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

# 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 <= 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 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:

‍To learn more, register for the FREE webinar.

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*