Problem

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 "".

OR

Given a sentence, give Longest Sequence Of Prefix Shared By All The Words In A String

Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.

As an example, longest common prefix of “abcdefgh” and “abcefgh” is “abc”.

This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.

Examples

Example 1:

1
2

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution

Method 1 - Using indexOf

To find the longest common prefix among an array of strings, we can follow these steps:

  1. Edge Cases: Handle edge cases where the input array is empty or contains only one string.
  2. Horizontal Scanning: Compare characters of each string in the array sequentially, checking for the common prefix.
1
2
3

Small Optimization

We can do a small optimization in this approach. Instead of starting with resultLen of arr[0].length, we can take length of the smallest string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // Start with the first string in the array as the prefix
        String prefix = strs[0];

        // Traverse the remaining strings in the array
        for (int i = 1; i < strs.length; i++) {
            // Update the prefix by comparing with the succeeding strings
            while (strs[i].indexOf(prefix) != 0) {
                // Reduce the prefix by one character at a time until it matches
                prefix = prefix.substring(0, prefix.length() - 1);

                // If the prefix becomes empty, there's no common prefix
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix;
    }

}

Complexity

  • ⏰ Time complexity: O(n * m) where n is the number of strings and m is length of string
  • 🧺 Space complexity: O(1)