Jobs

Interviews

Discussions

Longest Common Prefix

Easy

Asked by:

+27

More companies

627 views

Topics:

ArraysStrings

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

Example 1:

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

Example 2:

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

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Try coding it in LeetCode

Longest Common Prefix

Easy

Asked by:

+21

More companies

627 views

Topics:

ArraysStrings

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

Example 1:

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

Example 2:

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

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input array and the length of the strings within the array?
Can the input array be empty? If so, what should be returned?
Can any of the strings in the input array be empty? If so, how should that be handled?
Are the strings guaranteed to contain only lowercase English letters, or can they include other characters (e.g., uppercase, numbers, symbols)?
If all strings are identical, should the entire string be returned as the common prefix?

Brute Force Solution

Approach

This problem asks for the longest string that appears at the beginning of every word in a given collection of words. The brute force method simply checks every possible starting part of a word to see if it's common to all the other words.

Here's how the algorithm would work step-by-step:

Pick the very first word as a reference.
Consider the first letter of that first word. Check if this letter is also the first letter of all the other words.
If it is, then consider the first two letters of the first word. Check if this two-letter combination is the start of all the other words.
Continue this process, adding one letter at a time from the first word, and checking if that growing combination is present at the start of every single word in the collection.
Stop as soon as you find a combination that is NOT at the start of even one of the other words.
The longest combination that *was* at the start of all the words before you stopped is your answer.

Code Implementation

def longestCommonPrefix(list_of_strings):    if not list_of_strings:        return ""    # The first string in the list will serve as our reference for building the prefix    reference_string = list_of_strings[0]    for prefix_length in range(1, len(reference_string) + 1):        potential_prefix = reference_string[:prefix_length]        # For each potential prefix, we must verify it's at the start of ALL other strings        is_common_to_all = True        for i in range(1, len(list_of_strings)):            current_string = list_of_strings[i]            # If the current string is shorter than the potential prefix or doesn't start with it, it's not common            if len(current_string) < prefix_length or current_string[:prefix_length] != potential_prefix:                is_common_to_all = False                break        # If the potential prefix was not common to all strings, the previous prefix was the longest common one        if not is_common_to_all:            return reference_string[:prefix_length - 1]    # If the loop completes, the entire reference string is the longest common prefix    return reference_string

Big(O) Analysis

Time Complexity

O(S) – Let n be the number of strings in the input array, and let m be the length of the shortest string. The algorithm iterates through each character of the first string (up to length m) and for each character, it iterates through all n strings to check if the character matches. In the worst case, we might compare all characters of the shortest string across all n strings. Therefore, the total number of character comparisons is at most n * m. If we denote the total number of characters in all strings as S, then m <= S. The runtime complexity is thus proportional to the total number of characters examined, which is O(S).

Space Complexity

O(1) – The described approach primarily uses a few variables to keep track of the current prefix being checked and loop indices. No additional data structures that grow with the input size (number of words or their lengths) are explicitly created. Therefore, the auxiliary space complexity remains constant, independent of the input size.

Optimal Solution

Approach

The fastest way to find the longest common prefix is to compare the words in a way that eliminates possibilities quickly. Instead of comparing every character of every word against every other word, we can focus on how the words start and stop matching.

Here's how the algorithm would work step-by-step:

Imagine you have a list of words.
Pick the very first word in the list as a starting point for what the common prefix might be.
Now, go through the rest of the words one by one.
For each word, see how much of it matches the current potential common prefix you have in mind, starting from the beginning.
If a word doesn't match the potential prefix at all, or if it only matches for a shorter length, you'll have to shorten your potential common prefix to match that shorter length.
Keep doing this for every word. Each time you find a shorter match, you update your idea of the longest possible common prefix.
Once you've checked all the words, whatever is left of your potential common prefix is the longest one that all the words share.
If at any point your potential common prefix becomes completely empty, you know there's no common prefix at all, so you can stop early.

Code Implementation

def find_longest_common_prefix(list_of_strings):
    if not list_of_strings:
        return ""

    potential_common_prefix = list_of_strings[0]

    # We iterate through the rest of the strings, comparing them against the current prefix.
    for current_string_index in range(1, len(list_of_strings)):
        current_string = list_of_strings[current_string_index]
        current_prefix_length = 0
        
        # This loop finds the maximum length of the prefix that matches between the potential prefix and the current string.
        while current_prefix_length < len(potential_common_prefix) and current_prefix_length < len(current_string) and potential_common_prefix[current_prefix_length] == current_string[current_prefix_length]:
            current_prefix_length += 1
        
        # If a string doesn't match the current prefix at all, we shorten the potential prefix.
        potential_common_prefix = potential_common_prefix[:current_prefix_length]

        # If the potential prefix becomes empty, there's no common prefix for all strings.
        if not potential_common_prefix:
            break

    # The remaining potential_common_prefix is the longest shared prefix among all strings.
    return potential_common_prefix

Big(O) Analysis

Time Complexity

O(S) – Let n be the number of strings in the input array and m be the length of the shortest string. In the described approach, we iterate through each string in the input array (n strings). For each string, we compare it character by character with the current shortest common prefix. In the worst case, we might compare up to m characters for each of the n strings. The total number of character comparisons is at most n * m, where m is the length of the shortest string. Therefore, the time complexity is proportional to the total number of characters in the input strings if we consider the sum of lengths of all strings, or more precisely, it's bounded by the number of strings multiplied by the length of the shortest string. Let S be the total number of characters across all strings. The algorithm effectively checks characters until a mismatch is found or the shortest string is exhausted. The total operations approximate S in the worst case, simplifying to O(S).

Space Complexity

O(1) – The algorithm uses a constant amount of auxiliary space. It primarily relies on a few variables to store the current potential common prefix, its length, and loop indices. The size of these variables does not depend on the number of words (N) in the input list. Therefore, the extra memory usage remains constant regardless of the input size, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Input array is empty	If the input array is empty, return an empty string as there are no strings to compare.
Input array contains only one string	If the input array has only one string, that string is the longest common prefix.
Input array contains empty strings	If any string in the input array is empty, the longest common prefix must be an empty string.
All strings in the input array are identical	The algorithm will correctly identify the entire string as the longest common prefix.
No common prefix exists among the strings	The algorithm will naturally terminate with an empty string if no common characters are found at the beginning.
Very long strings or a large number of strings	Efficiency is important; iterating character by character or sorting can be optimized to handle larger inputs within typical time limits.
Strings with varying lengths	The comparison should stop at the length of the shortest string to avoid index out of bounds errors.
Input array contains null values	A robust solution should handle null strings by treating them as if they have no characters, effectively making the common prefix empty.

Input array is empty

How to Handle:

If the input array is empty, return an empty string as there are no strings to compare.

Input array contains only one string

How to Handle:

If the input array has only one string, that string is the longest common prefix.

Input array contains empty strings

How to Handle:

If any string in the input array is empty, the longest common prefix must be an empty string.

All strings in the input array are identical

How to Handle:

The algorithm will correctly identify the entire string as the longest common prefix.

No common prefix exists among the strings

How to Handle:

The algorithm will naturally terminate with an empty string if no common characters are found at the beginning.

Very long strings or a large number of strings

How to Handle:

Efficiency is important; iterating character by character or sorting can be optimized to handle larger inputs within typical time limits.

Strings with varying lengths

How to Handle:

The comparison should stop at the length of the shortest string to avoid index out of bounds errors.

Input array contains null values

How to Handle:

A robust solution should handle null strings by treating them as if they have no characters, effectively making the common prefix empty.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input array and the length of the strings within the array?
Can the input array be empty? If so, what should be returned?
Can any of the strings in the input array be empty? If so, how should that be handled?
Are the strings guaranteed to contain only lowercase English letters, or can they include other characters (e.g., uppercase, numbers, symbols)?
If all strings are identical, should the entire string be returned as the common prefix?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick the very first word as a reference.
Consider the first letter of that first word. Check if this letter is also the first letter of all the other words.
If it is, then consider the first two letters of the first word. Check if this two-letter combination is the start of all the other words.
Continue this process, adding one letter at a time from the first word, and checking if that growing combination is present at the start of every single word in the collection.
Stop as soon as you find a combination that is NOT at the start of even one of the other words.
The longest combination that *was* at the start of all the words before you stopped is your answer.

Code Implementation

def longestCommonPrefix(list_of_strings):    if not list_of_strings:        return ""    # The first string in the list will serve as our reference for building the prefix    reference_string = list_of_strings[0]    for prefix_length in range(1, len(reference_string) + 1):        potential_prefix = reference_string[:prefix_length]        # For each potential prefix, we must verify it's at the start of ALL other strings        is_common_to_all = True        for i in range(1, len(list_of_strings)):            current_string = list_of_strings[i]            # If the current string is shorter than the potential prefix or doesn't start with it, it's not common            if len(current_string) < prefix_length or current_string[:prefix_length] != potential_prefix:                is_common_to_all = False                break        # If the potential prefix was not common to all strings, the previous prefix was the longest common one        if not is_common_to_all:            return reference_string[:prefix_length - 1]    # If the loop completes, the entire reference string is the longest common prefix    return reference_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a list of words.
Pick the very first word in the list as a starting point for what the common prefix might be.
Now, go through the rest of the words one by one.
For each word, see how much of it matches the current potential common prefix you have in mind, starting from the beginning.
If a word doesn't match the potential prefix at all, or if it only matches for a shorter length, you'll have to shorten your potential common prefix to match that shorter length.
Keep doing this for every word. Each time you find a shorter match, you update your idea of the longest possible common prefix.
Once you've checked all the words, whatever is left of your potential common prefix is the longest one that all the words share.
If at any point your potential common prefix becomes completely empty, you know there's no common prefix at all, so you can stop early.

Code Implementation

def find_longest_common_prefix(list_of_strings):
    if not list_of_strings:
        return ""

    potential_common_prefix = list_of_strings[0]

    # We iterate through the rest of the strings, comparing them against the current prefix.
    for current_string_index in range(1, len(list_of_strings)):
        current_string = list_of_strings[current_string_index]
        current_prefix_length = 0
        
        # This loop finds the maximum length of the prefix that matches between the potential prefix and the current string.
        while current_prefix_length < len(potential_common_prefix) and current_prefix_length < len(current_string) and potential_common_prefix[current_prefix_length] == current_string[current_prefix_length]:
            current_prefix_length += 1
        
        # If a string doesn't match the current prefix at all, we shorten the potential prefix.
        potential_common_prefix = potential_common_prefix[:current_prefix_length]

        # If the potential prefix becomes empty, there's no common prefix for all strings.
        if not potential_common_prefix:
            break

    # The remaining potential_common_prefix is the longest shared prefix among all strings.
    return potential_common_prefix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is empty	If the input array is empty, return an empty string as there are no strings to compare.
Input array contains only one string	If the input array has only one string, that string is the longest common prefix.
Input array contains empty strings	If any string in the input array is empty, the longest common prefix must be an empty string.
All strings in the input array are identical	The algorithm will correctly identify the entire string as the longest common prefix.
No common prefix exists among the strings	The algorithm will naturally terminate with an empty string if no common characters are found at the beginning.
Very long strings or a large number of strings	Efficiency is important; iterating character by character or sorting can be optimized to handle larger inputs within typical time limits.
Strings with varying lengths	The comparison should stop at the length of the shortest string to avoid index out of bounds errors.
Input array contains null values	A robust solution should handle null strings by treating them as if they have no characters, effectively making the common prefix empty.

Input array is empty

How to Handle:

If the input array is empty, return an empty string as there are no strings to compare.

Input array contains only one string

How to Handle:

If the input array has only one string, that string is the longest common prefix.

Input array contains empty strings

How to Handle:

If any string in the input array is empty, the longest common prefix must be an empty string.

All strings in the input array are identical

How to Handle:

The algorithm will correctly identify the entire string as the longest common prefix.

No common prefix exists among the strings

How to Handle:

The algorithm will naturally terminate with an empty string if no common characters are found at the beginning.

Very long strings or a large number of strings

How to Handle:

Efficiency is important; iterating character by character or sorting can be optimized to handle larger inputs within typical time limits.

Strings with varying lengths

How to Handle:

The comparison should stop at the length of the shortest string to avoid index out of bounds errors.

Input array contains null values

How to Handle:

A robust solution should handle null strings by treating them as if they have no characters, effectively making the common prefix empty.