Domain 1EasyCORE

Longest Common Prefix

The problem requires finding the longest common prefix string amongst an array of strings. The input is an array of strings, and the output should be the longest prefix that is common to all strings in the array. If there is no common prefix, the function should return an empty string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

14. Longest Common Prefix

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 36.2%


Problem Breakdown

The problem requires finding the longest common prefix string amongst an array of strings. The input is an array of strings, and the output should be the longest prefix that is common to all strings in the array. If there is no common prefix, the function should return an empty string.

Inputs:

  • An array of strings strs.

Outputs:

  • A string representing the longest common prefix among the input strings.

Implicit Constraints and Edge Cases:

  • The array can be empty.
  • Strings in the array can be empty.
  • All strings consist of only lowercase English letters.

Intuition

A brute-force approach would involve comparing each character of every string at each position until a mismatch is found. This approach has a high time complexity, especially for large arrays and long strings.

The key insight to improve this is to realize that the longest common prefix cannot be longer than the shortest string in the array. Therefore, we can compare characters of all strings up to the length of the shortest string. If at any point, a character does not match across all strings at the same position, we stop and return the substring up to that point.

Approach

  1. Check for Empty Input: If the input array is empty, return an empty string immediately.
  2. Find the Shortest String: Determine the shortest string in the array as this will limit the length of the common prefix.
  3. Iterate and Compare Characters:
    • For each character position up to the length of the shortest string:
      • Compare the character at that position across all strings.
      • If a mismatch is found, return the substring from the start up to the current position.
  4. Return the Shortest String: If no mismatches are found, the entire shortest string is the common prefix.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of strings and m is the length of the shortest string. This is because we potentially compare each character of each string up to the length of the shortest string.
  • Space Complexity: O(1) for the additional space used, excluding the input and output.

Solution

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    # Find the shortest string in the array
    min_length = min(len(s) for s in strs)
    
    # Iterate over each character position up to the length of the shortest string
    for i in range(min_length):
        # Compare characters at the current position across all strings
        char = strs[0][i]
        if any(s[i] != char for s in strs):
            # Return the substring from the start up to the current position
            return strs[0][:i]
    
    # If no mismatches are found, return the entire shortest string
    return strs[0]

# Example usage:
# print(longestCommonPrefix(["flower","flow","flight"]))  # Output: "fl"
# print(longestCommonPrefix(["dog","racecar","car"]))     # Output: ""

Edge Cases Handled

  • Empty Input Array: The function returns an empty string immediately.
  • All Strings Empty: The function correctly handles this by returning an empty string.
  • No Common Prefix: The function returns an empty string when no common prefix exists.
  • Single String in Array: The function returns the string itself as the longest common prefix.