Find Longest Common Prefix

Solving any problem requires one to analyze various available solutions and then look at factors like space complexity, time complexity, and ease of development.

Problem statement: Find the longest common prefix from N number of Strings.

Example: “kamal”, “kamalmeet”, “kamaljeet” should return “kamal”

Solution 1- Vertical Scanning

Approach: Start with the first element of each string and compare for equality. Continue till a point we do not find the same character.

Pseudo code:

-- for i=0 to n, of the length of the first (any) string
---- check if ith character is equal for all string
------ if not, return string from 0 to i-1 character


    public String longestCommonPrefix(String[] strs) {
        for (int index = 0; index < strs[0].length(); index++) {
            char ch = strs[0].charAt(index);
            for (String st : strs) {
                // one of the strings has ended or char mismatch found
                if (index >= st.length() || st.charAt(index) != ch) {
                    return strs[0].substring(0, index);
        // if you reached here, first string is longest common prefix
        return strs[0];

Time Complexity: O(S) for Worst case all strings are equal, and S is the sum of all string lengths

Space Complexity: O(1) no additional data structure

Solution 2 – Horizontal Scanning

Approach: Start by comparing the first two strings and find the longest common prefix. Use this as input and compare it with next string and so on.

Pseudo code:

-- longestprefix = str[0]
-- for strings in i=1 to N
---- longestprefix = findlongestprefix(longestprefix, str[i])
-- return longestprefix

Time Complexity: O(S)

Space complexity: O(1)

Solution 3- Divide and Conquer

Approach: Break down the array of strings into two equal parts, solve for the two subarrays, and find a solution for two results (repeat the process at each step).


Additional Approaches