[Solved] How to find the Longest common prefix in Array of String in Java? Example Tutorial

Hello guys, If you are preparing for technical interviews and wondering how to solve the longest common prefix in a given array of String problems in Java then you have come to the right place. Earlier, I have shared 21 String programming problems and one of them was this one. In this article, I am going to show you how to solve this frequently asked coding problem from Java Interviews. It's one of the difficult coding problems and not every programmer I have interviewed has solved this, only a few can solve this so preparing for this one can definitely improve your chances and give you a competitive edge over other candidates.

But, today we are not gonna see any usual Java class or any method.  Today we are gonna put our minds to use and write some code in java to calculate the Longest Common Prefix between a set of strings. we will discuss 2 approaches for the same and will see what is the complexity, how we can improve it, and what lies ahead for you guys as hands-on.

First of all, let us understand what the problem is and what it has for us to understand. The best advice I can give you guys is that before trying to jump into writing the code, understand the question thoroughly and try to make up in mind the solution. If you are facing difficulties, grab a pen and paper and try to jot it down. so, what's the wait? let's start!

What is the Longest Common Prefix in an array of String?

Consider we have 'N' strings with us. We need to find the longest common prefix of those n strings.

The longest common prefix is defined as the longest substring which is common to all the strings and that too is a prefix. A bit of confusion? don't worry. let us break down the words and understand what each one means.

A prefix is a set from the beginning. So, taking an example, let's say there is a string s = "Longest"

Now, it's prefix can be {"L", "Lo", "Lon", "Long", "Longe", "Longes", "Longest"}. As seen, any size of substring from starting is a prefix. 

Now, in our problem, we need to find the longest prefix that is common to all the strings. Got it?

Let's understand more with the help of an example. Let's say we have 6 strings as mentioned below:

• FastAndFurious
• FastAndFuriousAgain
• FastAndVeryFurious
• FastButNotFurious
• FasterAndFurious
• FastestAndReckless

Now, get paper and pen and try it out yourself. Find the longest common prefix. take 2 minutes and solve it.

Now, for those who have solved. What is the answer? What is the longest common prefix amongst these strings? Yes! the answer is "Fast". This substring is a prefix to all strings and is common and longest.

So, how did you do it? you may have an approach and we will see it later. For those who couldn't figure it out. No worries, let's discuss it.

This question can be solved using multiple techniques. Explaining all of those is out of scope for this article. But, we will try to understand a few of them which are capable of solving the question and have a decent complexity.

2. The Horizontal Scanning approach to find longest common Prefix

For this, we will scan horizontally, which means, we will first find the longest common prefix of 2 strings, then 3 strings, going on till 'N'. sounds simple right? It is! let us check this by writing a code and checking how the implementation works.

Coding Solution of Longest common prefix in a set of String

import java.util.Scanner;

public class LongestCommonPrefix {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the size of array:");
        int n = sc.nextInt();
        System.out.println("Enter the elements of array:");
        String[] array = new String[n];
        sc.nextLine();
        //be sure to not enter any space!
        for(int i=0;i<n;i++) {
            array[i] = sc.nextLine();
        }
        LongestCommonPrefix lcp = new LongestCommonPrefix();
        String longestCommonPrefix = lcp.findLongestCommonPrefix(array);
        System.out.print("the longest common prefix from these strings is: "
                 +longestCommonPrefix);

    }

    public String findLongestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                //System.out.println(strs[i]);
                //System.out.println(prefix);
                //System.out.println(strs[i].indexOf(prefix));
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        return prefix;
    }
}

Output:

After observing the code implementation and the output carefully, we can see how this works. Let me guide you on how this works. First, we keep the prefix as "FastAndFurious", which is, our first String in the array.

Now, we start a traversal from string 2 and check and update the prefix that is common to string 1 and 2, which is "FastAndFurious". we go ahead on the 3rd string, where we get "Fast" and so on.

After completing the final loop, we arrive at a state where all the strings are processed and we have our common prefix that is the longest! Tada! you guys can check the output and verify this. Also, feel free to perform a hands-on for the same.

Time complexity: O(K), where K = sum of all characters of all strings combined.

Space complexity: O(1)

Now, let's quickly move on to another method. 

3. The Vertical Scanning approach to find Longest Common Prefix in an Array of String in Java

In this approach, rather than checking for each string, we will work vertically, that is, we will check all the strings at once and get the longest common prefix. let's see the code for this too and how it works.

import java.util.Scanner;

public class LongestCommonPrefix {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the size of array:");
        int n = sc.nextInt();
        System.out.println("Enter the elements of array:");
        String[] array = new String[n];
        sc.nextLine();
        //be sure to not enter any space!
        for(int i=0;i<n;i++) {
            array[i] = sc.nextLine();
        }
        LongestCommonPrefix lcp = new LongestCommonPrefix();
        String longestCommonPrefix = lcp.findLongestCommonPrefix(array);
        System.out.print("the longest common prefix from these strings is: "
              +longestCommonPrefix);

    }

    public String findLongestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j ++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }
}

Output:

Time complexity: O(K), where K = sum of all characters of all strings combined.

Space complexity: O(1)

The output is exactly the same. you guys can go over the code and understand that the logic is very simple and as explained. Also, don't forget to try hand-on before copy-pasting :p

Till then, adios :p

Other Data Structure and Algorithms  You may like

• How to implement a recursive preorder algorithm in Java? (solution)
• 10 Courses to learn Data Structure in Java (courses)
• How to implement a binary search tree in Java? (solution)
• 7 Free Books to learn Data Structure and Algorithms (books)
• Post order binary tree traversal without recursion (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (list)
• 5 Books to Learn Data Structure and Algorithms in-depth (books) 
• How to reverse an array in Java? (solution)
• 75+ Coding Interview Questions for Programmers (questions)
• Recursive Post Order traversal Algorithm (solution)
• Iterative Pre Order traversal in a binary tree (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Recursive InOrder traversal Algorithm (solution)
• How to remove duplicate elements from the array in Java? (solution)
• 7 Best Courses to learn Data Structure and Algorithms (best courses)
• 10 Data Structure and Programming courses to crack interviews (courses)
• How to print leaf nodes of a binary tree without recursion? (solution)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this String coding interview problem about finding the longest common prefix in a given array of String, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structures in Java for Beginners course on Udemy. It's free and you just need a Udemy account to join this course.