Jobs

Interviews

Discussions

Longest Common Prefix

Easy

Apple

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

Longest Common Prefix

Easy

Apple

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

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 is the range of possible lengths for the strings in the input array?
Can the input array be empty or contain null/empty strings?
If there is no common prefix among all strings, what should the function return?
Are the strings in the array guaranteed to be ASCII or Unicode, or should I consider other character sets?
Is the input case-sensitive, meaning should 'Flower' and 'flower' be considered as sharing a common prefix of 'flower' (when the other string is 'flower')?

Brute Force Solution

Approach

The brute force approach to finding the longest common prefix is to compare the words character by character. We start by assuming the first word's initial part is the common prefix, and then we trim it down if needed by comparing it against the other words. We keep making it smaller until we find a common part or nothing is left.

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

Take the first word and assume that its whole beginning part is the longest common part.
Now, look at the next word. Compare the beginning part from step one with this word. How far do they match?
If they don't match at all, then there's nothing in common, so the longest common part is empty.
If they match for some part, shorten the 'longest common part' to only include the matching characters.
Do this for all the remaining words one by one, shrinking the 'longest common part' whenever a mismatch occurs.
After comparing with all the words, whatever is left in the 'longest common part' is the answer.

Code Implementation

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

    longest_common_part = list_of_strings[0]

    for string_index in range(1, len(list_of_strings)):
        current_string = list_of_strings[string_index]
        prefix_length = 0

        # Find the matching length between current prefix and string.
        for char_index in range(min(len(longest_common_part), len(current_string))):
            if longest_common_part[char_index] == current_string[char_index]:
                prefix_length += 1
            else:
                break

        # If no match, common prefix must be empty string
        if prefix_length == 0:
            return ""

        # Reduce longest common prefix to the matching part
        longest_common_part = longest_common_part[:prefix_length]

    return longest_common_part

Big(O) Analysis

Time Complexity

O(S) – Let n be the number of strings in the input array and S be the sum of all characters across all strings. The outer loop iterates through each character of the first string (at most S). The inner loop iterates through the remaining n-1 strings, and for each string, we compare at most the number of characters equal to the length of the current potential longest common prefix (which is bounded by S). Therefore, in the worst case where all strings have a long common prefix or are very similar, we are comparing characters across almost all strings, making the time complexity proportional to S. S can also be thought of as n*k in some situations, where k is the average size of each string.

Space Complexity

O(1) – The algorithm iteratively reduces the `longest common part` (which is a prefix of the first word) by comparing it with other words. However, according to the description, it operates by shortening the initial part in place, using no extra data structures to store intermediate results or copies of the prefix. Therefore, the space used remains constant, irrespective of the number of words (N) or their lengths. The space complexity is thus O(1).

Optimal Solution

Approach

The best way to find the longest common prefix is to compare the words one letter at a time. We stop as soon as we find a letter that is different between any of the words. This approach is efficient because it avoids unnecessary comparisons.

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

Take the first word in the list as a starting point.
Compare the first letter of the first word with the first letter of every other word.
If all the first letters match, move on to the second letter and repeat the process for all words.
Keep comparing letters at the same position in each word until you find a letter that doesn't match or you reach the end of one of the words.
Once you find a mismatch or reach the end of a word, the common prefix is all the letters up to that point.
Return the common prefix you've identified.

Code Implementation

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

    # Start with the first string as the potential prefix
    potential_prefix = list_of_strings[0]
    
    for index in range(len(potential_prefix)):
        character = potential_prefix[index]

        # Compare the current character with all other strings
        for other_string in list_of_strings[1:]:
            # Check if index is out of bounds for the other string
            if index >= len(other_string) or other_string[index] != character:
                # Mismatch found, return the prefix up to this point
                return potential_prefix[:index]

    # If all characters match, the first string is the prefix
    return potential_prefix

Big(O) Analysis

Time Complexity

O(S) – The time complexity is determined by the total number of characters (S) across all strings, not the number of strings. In the worst-case scenario, we iterate through the common prefix of all strings, comparing characters at each index. The outer loop iterates up to the length of the shortest string, and the inner loop iterates through the array of strings. Therefore, the overall complexity depends on the sum of lengths of the common prefixes across all the input strings. Thus, the time complexity can be expressed as O(S), where S is the total number of characters in the common prefix across all strings, bounded by the total number of characters in all strings.

Space Complexity

O(1) – The algorithm iterates through the input strings and compares characters directly without using any auxiliary data structures that scale with the input size. It uses a constant amount of extra space to store the index of the character being compared, and potentially the length of the longest common prefix found so far. Therefore, the auxiliary space complexity is constant, irrespective of the number of strings or their lengths.

Edge Cases

Case	How to Handle
Empty input array	Return an empty string immediately as there's no common prefix possible.
Array containing a single empty string	The longest common prefix will be the empty string itself.
Array with one string	The longest common prefix is the string itself.
Strings with no common prefix	The algorithm should correctly identify this and return an empty string.
Strings with different lengths, where one is a prefix of another	The shortest string is the longest possible common prefix, and the algorithm must handle it.
Very long strings in the input array (potential performance issues)	Consider optimizing for character-by-character comparison to avoid unnecessary operations.
Input strings with Unicode characters	Ensure the character comparison is Unicode-aware for correct results.
Array containing null or undefined string values	Handle null or undefined strings appropriately, possibly by throwing an error or treating them as empty strings.

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 is the range of possible lengths for the strings in the input array?
Can the input array be empty or contain null/empty strings?
If there is no common prefix among all strings, what should the function return?
Are the strings in the array guaranteed to be ASCII or Unicode, or should I consider other character sets?
Is the input case-sensitive, meaning should 'Flower' and 'flower' be considered as sharing a common prefix of 'flower' (when the other string is 'flower')?

Brute Force Solution

Approach

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

Take the first word and assume that its whole beginning part is the longest common part.
Now, look at the next word. Compare the beginning part from step one with this word. How far do they match?
If they don't match at all, then there's nothing in common, so the longest common part is empty.
If they match for some part, shorten the 'longest common part' to only include the matching characters.
Do this for all the remaining words one by one, shrinking the 'longest common part' whenever a mismatch occurs.
After comparing with all the words, whatever is left in the 'longest common part' is the answer.

Code Implementation

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

    longest_common_part = list_of_strings[0]

    for string_index in range(1, len(list_of_strings)):
        current_string = list_of_strings[string_index]
        prefix_length = 0

        # Find the matching length between current prefix and string.
        for char_index in range(min(len(longest_common_part), len(current_string))):
            if longest_common_part[char_index] == current_string[char_index]:
                prefix_length += 1
            else:
                break

        # If no match, common prefix must be empty string
        if prefix_length == 0:
            return ""

        # Reduce longest common prefix to the matching part
        longest_common_part = longest_common_part[:prefix_length]

    return longest_common_part

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Take the first word in the list as a starting point.
Compare the first letter of the first word with the first letter of every other word.
If all the first letters match, move on to the second letter and repeat the process for all words.
Keep comparing letters at the same position in each word until you find a letter that doesn't match or you reach the end of one of the words.
Once you find a mismatch or reach the end of a word, the common prefix is all the letters up to that point.
Return the common prefix you've identified.

Code Implementation

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

    # Start with the first string as the potential prefix
    potential_prefix = list_of_strings[0]
    
    for index in range(len(potential_prefix)):
        character = potential_prefix[index]

        # Compare the current character with all other strings
        for other_string in list_of_strings[1:]:
            # Check if index is out of bounds for the other string
            if index >= len(other_string) or other_string[index] != character:
                # Mismatch found, return the prefix up to this point
                return potential_prefix[:index]

    # If all characters match, the first string is the prefix
    return potential_prefix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty string immediately as there's no common prefix possible.
Array containing a single empty string	The longest common prefix will be the empty string itself.
Array with one string	The longest common prefix is the string itself.
Strings with no common prefix	The algorithm should correctly identify this and return an empty string.
Strings with different lengths, where one is a prefix of another	The shortest string is the longest possible common prefix, and the algorithm must handle it.
Very long strings in the input array (potential performance issues)	Consider optimizing for character-by-character comparison to avoid unnecessary operations.
Input strings with Unicode characters	Ensure the character comparison is Unicode-aware for correct results.
Array containing null or undefined string values	Handle null or undefined strings appropriately, possibly by throwing an error or treating them as empty strings.