Longest Common Prefix: Complete Guide

Have you ever noticed how some words start the same way? For example, "flower," "flow," and "flight" all begin with "fl." This shared beginning is known as a prefix. Finding common prefixes is not just interesting; it’s a useful task in many areas of life, from organizing files on your computer to searching through data. Imagine you and your friends all have names starting with the same letters, like "Alice," "Alison," and "Alex." Those shared letters are your common prefix!

Problem statement

You are given an array of strings. Your task is to find the longest common prefix among all the strings in the array. If there is no common prefix, return an empty string "".

Sample input

1input_strings = ["flower", "flow", "flight"]

Sample Output

1output_string = "fl"

Understanding the problem

Finding the longest common prefix might seem simple, but it’s a great exercise in understanding how strings work in programming. When we talk about a "common prefix," we’re looking for the part at the beginning of each string that is the same across all the strings in the list. If no such part exists, then there’s no common prefix.

Imagine you’re organizing a group of friends into teams based on the first few letters of their names. If their names start the same way, they go into the same team. But if their names start differently, they can’t be grouped together. This is similar to what we’re doing with strings—grouping them based on their common starting letters.

Brute force approach

The simplest way to find the longest common prefix is to start with the first string in the array and compare it with each of the other strings one by one. You look for the longest part at the beginning that is the same in all the strings. If you find a mismatch, you shorten the prefix and try again until you find the longest one that works.

A smarter approach

A more efficient way to solve this problem is to start by finding the shortest string in the list since the longest possible prefix cannot be longer than the shortest string. Then, you can compare each string against this potential prefix and shorten it if necessary until you find the longest common prefix.

Pseudocode

Let’s break down the solution into simple steps:

• If the array is empty, return an empty string "".
• Start with the first string as the initial prefix.
• Loop through the remaining strings in the array:
  • While the current string does not start with the prefix, shorten the prefix by one character.
• If the prefix becomes empty during this process, return an empty string.
• Return the final prefix after the loop completes.

Python code

Here’s the complete Python code to find the longest common prefix:

1def longest_common_prefix(strs):
2    if not strs:
3        return ""
4    
5    # Start with the first string as the common prefix
6    common_prefix = strs[0]
7    
8    for s in strs[1:]:
9        while not s.startswith(common_prefix):
10            common_prefix = common_prefix[:-1]
11            if not common_prefix:
12                return ""
13    
14    return common_prefix
15
16# Sample input
17input_strings = ["flower", "flow", "flight"]
18# Calling the function and printing the result
19output_string = longest_common_prefix(input_strings)
20print("Longest Common Prefix:", output_string)

Explanation

• We begin by assuming the first string in the array is the common prefix.
• We then compare this prefix with each subsequent string in the array.
• If a string does not start with the current prefix, we shorten the prefix and try again.
• If the prefix becomes empty, we return "", indicating there is no common prefix.
• Otherwise, we return the final value of the prefix after all comparisons.

Java code

1public class LongestCommonPrefix {
2    public String longestCommonPrefix(String[] strs) {
3        if (strs.length == 0) return "";
4        
5        String prefix = strs[0];
6        for (int i = 1; i < strs.length; i++) {
7            while (strs[i].indexOf(prefix) != 0) {
8                prefix = prefix.substring(0, prefix.length() - 1);
9                if (prefix.isEmpty()) return "";
10            }
11        }
12        return prefix;
13    }
14}

Explanation

• In Java, we start with the first string as the initial prefix.
• We then compare this prefix with each subsequent string using indexOf to check if the string starts with the prefix.
• If a string does not match the prefix, we shorten the prefix by one character and continue the comparison.
• If the prefix becomes empty, we return an empty string "".
• Otherwise, we return the final prefix.

C++ code

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    std::string longestCommonPrefix(std::vector<std::string>& strs) {
7        if (strs.empty()) return "";
8        
9        std::string prefix = strs[0];
10        for (int i = 1; i < strs.size(); i++) {
11            while (strs[i].find(prefix) != 0) {
12                prefix = prefix.substr(0, prefix.length() - 1);
13                if (prefix.empty()) return "";
14            }
15        }
16        return prefix;
17    }
18};

Explanation

• In C++, we use a similar approach by starting with the first string as the prefix.
• We use the find function to check if each string starts with the current prefix.
• If not, we shorten the prefix and continue the comparison.
• If the prefix becomes empty, we return "".
• Otherwise, we return the final common prefix.

Efficient approach

The brute force methods we discussed are straightforward and work well, but we can also consider more efficient ways to solve the problem, such as using vertical scanning or divide and conquer. However, the approach we used already provides a good balance of simplicity and efficiency.

Python code

1def longest_common_prefix(strs):
2    if not strs:
3        return ""
4    
5    for i in range(len(strs[0])):
6        char = strs[0][i]
7        for string in strs[1:]:
8            if i >= len(string) or string[i] != char:
9                return strs[0][:i]
10    
11    return strs[0]

Explanation

• Instead of comparing entire strings, we compare character by character vertically across all strings.
• If we find a mismatch or reach the end of a string, we return the prefix found so far.
• This approach is efficient and easy to understand.

Java code

1public class LongestCommonPrefix {
2    public String longestCommonPrefix(String[] strs) {
3        if (strs == null || strs.length == 0) return "";
4        
5        for (int i = 0; i < strs[0].length(); i++) {
6            char c = strs[0].charAt(i);
7            for (int j = 1; j < strs.length; j++) {
8                if (i == strs[j].length() || strs[j].charAt(i) != c) {
9                    return strs[0].substring(0, i);
10                }
11            }
12        }
13        return strs[0];
14    }
15}

C++ code

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    std::string longestCommonPrefix(std::vector<std::string>& strs) {
7        if (strs.empty()) return "";
8        
9        for (int i = 0; i < strs[0].length(); i++) {
10            char c = strs[0][i];
11            for (int j = 1; j < strs.size(); j++) {
12                if (i == strs[j].length() || strs[j][i] != c) {
13                    return strs[0].substr(0, i);
14                }
15            }
16        }
17        return strs[0];
18    }
19};

Explanation

• In all three languages, this approach efficiently checks each character position across all strings until a mismatch is found.
• It returns the longest common prefix that matches up to the point where the first difference is encountered.

Conclusion

Finding the longest common prefix among a list of strings is a useful exercise in understanding string manipulation. Whether you're organizing names, searching through data, or simply solving coding challenges, this problem provides a solid foundation for working with strings.

By understanding both brute force and efficient approaches, you can confidently solve the "Longest Common Prefix" problem in various programming languages. Remember, practice makes perfect, and the more you work on problems like these, the better you'll become at thinking critically and solving complex tasks.