Jobs

Interviews

Discussions

Longest Common Prefix

Easy

Visa

0 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

Visa

0 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 maximum length of the input array `strs`?
Can the input strings be empty, or contain characters other than standard alphanumeric characters?
If the input array `strs` is empty or null, what should the function return?
Are the strings in the input array case-sensitive, or should I treat them as case-insensitive when comparing?
If multiple longest common prefixes exist, should I return any one of them, or is there a specific condition to choose one?

Brute Force Solution

Approach

The goal is to find the longest string that appears at the beginning of every word in a given list. The brute force method achieves this by exhaustively comparing each possible prefix against all the words in the list. We start with the shortest possible prefix and extend it until we find a mismatch.

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

Take the first word in the list.
Start with the first letter of that word. This is our potential common prefix.
Check if every other word in the list also starts with this letter.
If they all do, then extend the potential common prefix by one more letter from the first word.
Repeat the checking process with the new, longer potential common prefix.
If, at any point, even one word doesn't start with the current potential common prefix, then you've gone too far. The previous prefix was the longest one.
If you reach the end of the first word and all other words still match, then the entire first word is the longest common prefix.
Return the longest common prefix you found.

Code Implementation

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

    first_word = list_of_strings[0]
    longest_common_prefix = ""

    for index in range(1, len(first_word) + 1):
        potential_prefix = first_word[0:index]

        # Iterate through all other strings in the list
        for other_string in list_of_strings[1:]:
            # Check if current string starts with prefix
            if not other_string.startswith(potential_prefix):
                # If a mismatch occurs, return

                return longest_common_prefix

        # If all strings contain prefix, then update
        longest_common_prefix = potential_prefix

    return longest_common_prefix

Try it yourself on LeetCode

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 in the array. In the worst-case scenario, we iterate through the characters of the first string (up to a maximum of m characters) and, for each character, we compare it against the corresponding characters in the other n-1 strings. The total number of character comparisons will be proportional to the sum of lengths of the prefixes being compared across all strings. Therefore, the worst-case time complexity is O(S), where S is the sum of all the character lengths of the common prefix for each string in the input array.

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it uses only a few constant-size variables to store the potential common prefix and to iterate through the words. It doesn't create any additional data structures that scale with the input size N, where N is the number of words in the list or the length of the words. The algorithm operates in place, making only comparisons and updating the prefix length without requiring extra memory proportional to the input. Therefore, the auxiliary space remains constant regardless of the input size.

Optimal Solution

Approach

The most efficient way to find the longest common prefix is to compare the words in a smart way, one letter at a time. We'll start with the first word and see how much of it matches the beginning of all the other words.

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

Take the first word in the list as a starting point.
Look at the first letter of that word and check if all other words start with the same letter.
If they do, move on to the second letter and repeat the check across all words.
Keep going letter by letter until you find a letter that isn't the same across all words or you reach the end of the first word.
The part of the first word that matched all the other words is your longest common prefix.

Code Implementation

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

    prefix = list_of_strings[0]
    
    # Iterate through the characters of the first string.
    for character_index in range(len(prefix)):
        character = prefix[character_index]
        
        # Compare char with the chars in other strings.
        for string_index in range(1, len(list_of_strings)):
            # If the current string is shorter or chars don't match.
            if character_index >= len(list_of_strings[string_index]) or \
               list_of_strings[string_index][character_index] != character:

                # Return the prefix up to the current index.
                return prefix[:character_index]

    # If the first word is the prefix.
    return prefix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(S) – The outer loop iterates at most the length of the shortest string in the input array, which we can represent as S. The inner loop iterates through the array of strings, which has a length n. Therefore, in the worst-case scenario, where all strings share a long common prefix, we perform S * n comparisons. Thus, the time complexity is O(S), where S represents the total number of characters across all strings sharing the prefix.

Space Complexity

O(1) – The algorithm operates primarily by comparing characters in place. It uses a few constant space variables to iterate through the strings and track the length of the common prefix. No auxiliary data structures like arrays, lists, or hash maps are created. Therefore, the extra space used by the algorithm remains constant regardless of the input string array size.

Edge Cases

Case	How to Handle
Empty input array	Return an empty string immediately, as there are no strings to compare.
Array containing only an empty string	Return an empty string, as an empty string is the longest common prefix.
Array containing strings of different lengths where the shortest string is empty	Return an empty string, as no prefix can be formed.
Array with one string	Return the single string itself, as it is trivially the longest common prefix.
All strings are identical	Return any of the strings, as they are all the longest common prefix.
No common prefix exists	Return an empty string when the loop completes without finding a common prefix.
Very long strings with a short common prefix	The algorithm should efficiently find the short prefix without needing to compare the entire long strings.
Array with null strings	Handle null string inputs by either skipping them or throwing an exception, depending on requirements (skipping is often safer).

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 maximum length of the input array `strs`?
Can the input strings be empty, or contain characters other than standard alphanumeric characters?
If the input array `strs` is empty or null, what should the function return?
Are the strings in the input array case-sensitive, or should I treat them as case-insensitive when comparing?
If multiple longest common prefixes exist, should I return any one of them, or is there a specific condition to choose one?

Brute Force Solution

Approach

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

Take the first word in the list.
Start with the first letter of that word. This is our potential common prefix.
Check if every other word in the list also starts with this letter.
If they all do, then extend the potential common prefix by one more letter from the first word.
Repeat the checking process with the new, longer potential common prefix.
If, at any point, even one word doesn't start with the current potential common prefix, then you've gone too far. The previous prefix was the longest one.
If you reach the end of the first word and all other words still match, then the entire first word is the longest common prefix.
Return the longest common prefix you found.

Code Implementation

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

    first_word = list_of_strings[0]
    longest_common_prefix = ""

    for index in range(1, len(first_word) + 1):
        potential_prefix = first_word[0:index]

        # Iterate through all other strings in the list
        for other_string in list_of_strings[1:]:
            # Check if current string starts with prefix
            if not other_string.startswith(potential_prefix):
                # If a mismatch occurs, return

                return longest_common_prefix

        # If all strings contain prefix, then update
        longest_common_prefix = potential_prefix

    return longest_common_prefix

Try it yourself on LeetCode

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.
Look at the first letter of that word and check if all other words start with the same letter.
If they do, move on to the second letter and repeat the check across all words.
Keep going letter by letter until you find a letter that isn't the same across all words or you reach the end of the first word.
The part of the first word that matched all the other words is your longest common prefix.

Code Implementation

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

    prefix = list_of_strings[0]
    
    # Iterate through the characters of the first string.
    for character_index in range(len(prefix)):
        character = prefix[character_index]
        
        # Compare char with the chars in other strings.
        for string_index in range(1, len(list_of_strings)):
            # If the current string is shorter or chars don't match.
            if character_index >= len(list_of_strings[string_index]) or \
               list_of_strings[string_index][character_index] != character:

                # Return the prefix up to the current index.
                return prefix[:character_index]

    # If the first word is the prefix.
    return prefix

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty string immediately, as there are no strings to compare.
Array containing only an empty string	Return an empty string, as an empty string is the longest common prefix.
Array containing strings of different lengths where the shortest string is empty	Return an empty string, as no prefix can be formed.
Array with one string	Return the single string itself, as it is trivially the longest common prefix.
All strings are identical	Return any of the strings, as they are all the longest common prefix.
No common prefix exists	Return an empty string when the loop completes without finding a common prefix.
Very long strings with a short common prefix	The algorithm should efficiently find the short prefix without needing to compare the entire long strings.
Array with null strings	Handle null string inputs by either skipping them or throwing an exception, depending on requirements (skipping is often safer).