Jobs

Interviews

Discussions

Longest Common Prefix #20 Most Asked

Easy

Visa

12 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 #20 Most Asked

Easy

Visa

12 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 number of strings in the array and the length of each string?
Could the input array of strings be empty, or could it contain empty strings?
What is the character set of the strings? Are they all lowercase English letters, or can they include uppercase, numbers, or special symbols?
Is it possible for the input array to contain only a single string?
If the input array contains `null` or `undefined` values instead of strings, how should these be handled?

Brute Force Solution

Approach

The brute force strategy involves taking one word as a reference and then comparing every other word to it, one character at a time. We keep track of how many characters match up perfectly across all the words, starting from the very beginning.

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

First, pick the very first word from the list to be our standard for comparison.
Then, look at the first letter of this standard word.
Go through every other word in the list and check if their first letter is the same.
If all the first letters match, then we know the common part is at least one letter long. Now, let's check the second letter.
Look at the second letter of our standard word and compare it against the second letter of all the other words.
Continue this process, letter by letter, moving from left to right.
The moment you find a letter that doesn't match in any of the words, or if one of the words runs out of letters, you stop.
The common part is everything from the beginning of our standard word up to, but not including, the point where the mismatch occurred.

Code Implementation

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

    # Pick the very first word from the list to be our standard for comparison.
    reference_word = list_of_strings[0]

    # Iterate through each character of the reference word to check it against all other words.
    for character_index in range(len(reference_word)):
        current_character = reference_word[character_index]

        # Go through every other word in the list to check if their character matches.
        for word_index in range(1, len(list_of_strings)):
            current_word = list_of_strings[word_index]

            # If a word is shorter or a character mismatches, the common prefix ends here.
            if character_index >= len(current_word) or current_word[character_index] != current_character:
                return reference_word[:character_index]

    # If the loop completes, the entire first word is the common prefix.
    return reference_word

Big(O) Analysis

Time Complexity

O(n * m) – The time complexity is determined by two nested loops dictated by the input dimensions. We iterate through each character of the first string, which has a length we can denote as 'm'. For each of these 'm' characters, we must then scan through all 'n' strings in the input list to ensure the character matches. This character-by-character comparison across all strings results in a total number of operations proportional to the number of strings multiplied by the length of the common prefix. In the worst-case scenario, where the common prefix is the entire first string, the complexity is approximately n * m operations, which simplifies to O(n * m).

Space Complexity

O(1) – The algorithm operates by using a few variables to keep track of the current character index and the word being checked. Specifically, it needs one pointer or index for the character position in the reference word and another to iterate through the list of other words. The amount of memory for these variables does not grow with the number of strings or their length, making the auxiliary space usage constant.

Optimal Solution

Approach

The most efficient way to solve this is to realize the longest possible answer is just one of the words in the list. So, we can pick one word and carefully shorten it, character by character, until it matches the beginning of every other word in the list.

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

First, pick any word from the list to be our starting guess for the longest common prefix. Let's use the very first word in the list for simplicity.
Now, take this starting guess and compare it to the second word in the list.
If our guess doesn't perfectly match the beginning of the second word, we need to shorten our guess. We do this by removing the last character from our guess.
We keep shortening our guess, one character at a time, until it finally matches the beginning of the second word.
Once we have a guess that works for the second word, we move on to the third word in the list.
We repeat the process: compare our current guess to the third word, and shorten the guess if it doesn't match the beginning.
We continue this process for every single word in the list, always shortening our guess as needed.
Whatever is left of our initial guess after it has been successfully compared against every single word in the list is our final answer. If our guess becomes empty at any point, it means there is no common prefix at all.

Code Implementation

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

    # Start with the first word as the initial guess for the longest common prefix.

    longest_prefix_candidate = list_of_strings[0]

    for current_index in range(1, len(list_of_strings)):
        current_word_to_check = list_of_strings[current_index]

        # Shorten the prefix candidate until it matches the start of the current word.

        while not current_word_to_check.startswith(longest_prefix_candidate):
            longest_prefix_candidate = longest_prefix_candidate[:-1]

            # If the candidate becomes empty, no common prefix exists across all strings.

            if not longest_prefix_candidate:
                return ""

    # The remaining candidate is the longest prefix common to all strings.

    return longest_prefix_candidate

Big(O) Analysis

Time Complexity

O(n * m) – Let n be the number of strings in the list and m be the length of the first string. We iterate through each of the n strings in the list, from the second to the last. For each of these n strings, we perform a comparison with our current prefix, which has a maximum length of m. In the worst-case scenario, this comparison and subsequent shortening of the prefix can take up to m character comparisons for each of the n strings. Therefore, the total number of operations is proportional to the number of strings multiplied by the length of the initial string, which simplifies to O(n * m).

Space Complexity

O(1) – The algorithm operates by modifying a single variable that holds the current prefix guess, which is initially a reference to the first string. No new data structures like arrays or hash maps are created whose size depends on the number of strings or their lengths. The memory required for the prefix variable and loop counters is constant, regardless of the size of the input list. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
The input array of strings is null or empty	The function should return an empty string immediately as there are no strings to compare.
The input array contains only one string	The function should return that single string itself, as it is its own longest common prefix.
One or more strings in the array are empty	If any string is empty, the longest common prefix for the entire array must be an empty string.
All strings in the array are identical	The solution should correctly return any of the strings as the longest common prefix.
No common prefix exists among the strings	The function should correctly return an empty string when the very first characters differ.
The longest common prefix is one of the shorter strings in the array	The algorithm must not read past the end of the shortest string in the array.
Strings containing non-alphanumeric characters or different character sets	The character-by-character comparison approach handles any valid string characters, including symbols and Unicode.
A very large number of strings or very long strings	An efficient vertical scanning approach minimizes character comparisons and memory usage, scaling well with large inputs.

The input array of strings is null or empty

How to Handle:

The function should return an empty string immediately as there are no strings to compare.

The input array contains only one string

How to Handle:

The function should return that single string itself, as it is its own longest common prefix.

One or more strings in the array are empty

How to Handle:

If any string is empty, the longest common prefix for the entire array must be an empty string.

All strings in the array are identical

How to Handle:

The solution should correctly return any of the strings as the longest common prefix.

No common prefix exists among the strings

How to Handle:

The function should correctly return an empty string when the very first characters differ.

The longest common prefix is one of the shorter strings in the array

How to Handle:

The algorithm must not read past the end of the shortest string in the array.

Strings containing non-alphanumeric characters or different character sets

How to Handle:

The character-by-character comparison approach handles any valid string characters, including symbols and Unicode.

A very large number of strings or very long strings

How to Handle:

An efficient vertical scanning approach minimizes character comparisons and memory usage, scaling well with large inputs.

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 number of strings in the array and the length of each string?
Could the input array of strings be empty, or could it contain empty strings?
What is the character set of the strings? Are they all lowercase English letters, or can they include uppercase, numbers, or special symbols?
Is it possible for the input array to contain only a single string?
If the input array contains `null` or `undefined` values instead of strings, how should these be handled?

Brute Force Solution

Approach

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

First, pick the very first word from the list to be our standard for comparison.
Then, look at the first letter of this standard word.
Go through every other word in the list and check if their first letter is the same.
If all the first letters match, then we know the common part is at least one letter long. Now, let's check the second letter.
Look at the second letter of our standard word and compare it against the second letter of all the other words.
Continue this process, letter by letter, moving from left to right.
The moment you find a letter that doesn't match in any of the words, or if one of the words runs out of letters, you stop.
The common part is everything from the beginning of our standard word up to, but not including, the point where the mismatch occurred.

Code Implementation

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

    # Pick the very first word from the list to be our standard for comparison.
    reference_word = list_of_strings[0]

    # Iterate through each character of the reference word to check it against all other words.
    for character_index in range(len(reference_word)):
        current_character = reference_word[character_index]

        # Go through every other word in the list to check if their character matches.
        for word_index in range(1, len(list_of_strings)):
            current_word = list_of_strings[word_index]

            # If a word is shorter or a character mismatches, the common prefix ends here.
            if character_index >= len(current_word) or current_word[character_index] != current_character:
                return reference_word[:character_index]

    # If the loop completes, the entire first word is the common prefix.
    return reference_word

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, pick any word from the list to be our starting guess for the longest common prefix. Let's use the very first word in the list for simplicity.
Now, take this starting guess and compare it to the second word in the list.
If our guess doesn't perfectly match the beginning of the second word, we need to shorten our guess. We do this by removing the last character from our guess.
We keep shortening our guess, one character at a time, until it finally matches the beginning of the second word.
Once we have a guess that works for the second word, we move on to the third word in the list.
We repeat the process: compare our current guess to the third word, and shorten the guess if it doesn't match the beginning.
We continue this process for every single word in the list, always shortening our guess as needed.
Whatever is left of our initial guess after it has been successfully compared against every single word in the list is our final answer. If our guess becomes empty at any point, it means there is no common prefix at all.

Code Implementation

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

    # Start with the first word as the initial guess for the longest common prefix.

    longest_prefix_candidate = list_of_strings[0]

    for current_index in range(1, len(list_of_strings)):
        current_word_to_check = list_of_strings[current_index]

        # Shorten the prefix candidate until it matches the start of the current word.

        while not current_word_to_check.startswith(longest_prefix_candidate):
            longest_prefix_candidate = longest_prefix_candidate[:-1]

            # If the candidate becomes empty, no common prefix exists across all strings.

            if not longest_prefix_candidate:
                return ""

    # The remaining candidate is the longest prefix common to all strings.

    return longest_prefix_candidate

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The input array of strings is null or empty	The function should return an empty string immediately as there are no strings to compare.
The input array contains only one string	The function should return that single string itself, as it is its own longest common prefix.
One or more strings in the array are empty	If any string is empty, the longest common prefix for the entire array must be an empty string.
All strings in the array are identical	The solution should correctly return any of the strings as the longest common prefix.
No common prefix exists among the strings	The function should correctly return an empty string when the very first characters differ.
The longest common prefix is one of the shorter strings in the array	The algorithm must not read past the end of the shortest string in the array.
Strings containing non-alphanumeric characters or different character sets	The character-by-character comparison approach handles any valid string characters, including symbols and Unicode.
A very large number of strings or very long strings	An efficient vertical scanning approach minimizes character comparisons and memory usage, scaling well with large inputs.

The input array of strings is null or empty

How to Handle:

The function should return an empty string immediately as there are no strings to compare.

The input array contains only one string

How to Handle:

The function should return that single string itself, as it is its own longest common prefix.

One or more strings in the array are empty

How to Handle:

If any string is empty, the longest common prefix for the entire array must be an empty string.

All strings in the array are identical

How to Handle:

The solution should correctly return any of the strings as the longest common prefix.

No common prefix exists among the strings

How to Handle:

The function should correctly return an empty string when the very first characters differ.

The longest common prefix is one of the shorter strings in the array

How to Handle:

The algorithm must not read past the end of the shortest string in the array.

Strings containing non-alphanumeric characters or different character sets

How to Handle:

The character-by-character comparison approach handles any valid string characters, including symbols and Unicode.

A very large number of strings or very long strings

How to Handle:

An efficient vertical scanning approach minimizes character comparisons and memory usage, scaling well with large inputs.

0/0 Visa questions completed

0/0 completed