Longest Common Prefix

Find the longest common prefix string amongst an array of strings.

Language Selection

Choose your preferred programming language

Showing: Python

Longest Common Prefix

Problem Statement

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

Examples

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Explanation: The longest common prefix is "fl".

Example 2:

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

Example 3:

Input: strs = ["interspecies","interstellar","interstate"]
Output: "inters"
Explanation: The longest common prefix is "inters".

Constraints

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters

Approach 1: Vertical Scanning (Optimal)

Algorithm

Compare characters vertically (character by character across all strings) rather than horizontally (string by string).

Steps:

Take the first string as reference
For each character position, check if all strings have the same character
Stop when a mismatch is found or we reach the end of the shortest string

Implementation

Python:

def longestCommonPrefix(strs):
    """
    Find longest common prefix using vertical scanning
    Time: O(S) where S is the sum of all characters
    Space: O(1)
    """
    if not strs:
        return ""
    
    # Take first string as reference
    first_str = strs[0]
    
    # Check each character position
    for i in range(len(first_str)):
        char = first_str[i]
        
        # Check if all strings have the same character at position i
        for j in range(1, len(strs)):
            if i >= len(strs[j]) or strs[j][i] != char:
                return first_str[:i]
    
    return first_str

Java:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // Take first string as reference
        String firstStr = strs[0];
        
        // Check each character position
        for (int i = 0; i < firstStr.length(); i++) {
            char c = firstStr.charAt(i);
            
            // Check if all strings have the same character at position i
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return firstStr.substring(0, i);
                }
            }
        }
        
        return firstStr;
    }
}

Go:

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    
    // Take first string as reference
    firstStr := strs[0]
    
    // Check each character position
    for i := 0; i < len(firstStr); i++ {
        char := firstStr[i]
        
        // Check if all strings have the same character at position i
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || strs[j][i] != char {
                return firstStr[:i]
            }
        }
    }
    
    return firstStr
}

JavaScript:

function longestCommonPrefix(strs) {
    if (!strs || strs.length === 0) {
        return "";
    }
    
    // Take first string as reference
    const firstStr = strs[0];
    
    // Check each character position
    for (let i = 0; i < firstStr.length; i++) {
        const char = firstStr[i];
        
        // Check if all strings have the same character at position i
        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== char) {
                return firstStr.substring(0, i);
            }
        }
    }
    
    return firstStr;
}

C#:

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) {
            return "";
        }
        
        // Take first string as reference
        string firstStr = strs[0];
        
        // Check each character position
        for (int i = 0; i < firstStr.Length; i++) {
            char c = firstStr[i];
            
            // Check if all strings have the same character at position i
            for (int j = 1; j < strs.Length; j++) {
                if (i >= strs[j].Length || strs[j][i] != c) {
                    return firstStr.Substring(0, i);
                }
            }
        }
        
        return firstStr;
    }
}

Complexity Analysis

Time Complexity: O(S) - Where S is the sum of all characters in all strings
Space Complexity: O(1) - No extra space used

Approach 2: Horizontal Scanning

Algorithm

Compare strings one by one, finding the common prefix between the current result and the next string.

Steps:

Start with the first string as the initial prefix
For each subsequent string, find the common prefix with the current result
Update the result to be the common prefix found
Return empty string if no common prefix exists

Implementation

Python:

def longestCommonPrefixHorizontal(strs):
    """
    Find longest common prefix using horizontal scanning
    Time: O(S)
    Space: O(1)
    """
    if not strs:
        return ""
    
    # Start with first string as prefix
    prefix = strs[0]
    
    # Compare with each subsequent string
    for i in range(1, len(strs)):
        # Find common prefix between current prefix and current string
        while not strs[i].startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

Java:

public String longestCommonPrefixHorizontal(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    
    // Start with first string as prefix
    String prefix = strs[0];
    
    // Compare with each subsequent string
    for (int i = 1; i < strs.length; i++) {
        // Find common prefix between current prefix and current string
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) {
                return "";
            }
        }
    }
    
    return prefix;
}

Go:

func longestCommonPrefixHorizontal(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    
    // Start with first string as prefix
    prefix := strs[0]
    
    // Compare with each subsequent string
    for i := 1; i < len(strs); i++ {
        // Find common prefix between current prefix and current string
        for !strings.HasPrefix(strs[i], prefix) {
            prefix = prefix[:len(prefix)-1]
            if prefix == "" {
                return ""
            }
        }
    }
    
    return prefix
}

JavaScript:

function longestCommonPrefixHorizontal(strs) {
    if (!strs || strs.length === 0) {
        return "";
    }
    
    // Start with first string as prefix
    let prefix = strs[0];
    
    // Compare with each subsequent string
    for (let i = 1; i < strs.length; i++) {
        // Find common prefix between current prefix and current string
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") {
                return "";
            }
        }
    }
    
    return prefix;
}

C#:

public string LongestCommonPrefixHorizontal(string[] strs) {
    if (strs == null || strs.Length == 0) {
        return "";
    }
    
    // Start with first string as prefix
    string prefix = strs[0];
    
    // Compare with each subsequent string
    for (int i = 1; i < strs.Length; i++) {
        // Find common prefix between current prefix and current string
        while (!strs[i].StartsWith(prefix)) {
            prefix = prefix.Substring(0, prefix.Length - 1);
            if (string.IsNullOrEmpty(prefix)) {
                return "";
            }
        }
    }
    
    return prefix;
}

Complexity Analysis

Time Complexity: O(S) - Where S is the sum of all characters in all strings
Space Complexity: O(1) - No extra space used

Key Insights

Vertical vs Horizontal: Vertical scanning is often more efficient
Early Termination: Stop as soon as a mismatch is found
Edge Cases: Handle empty arrays and single strings
String Comparison: Efficient character-by-character comparison
Prefix Property: Common prefix can only get shorter, never longer

Edge Cases

Empty Array: Return empty string
Single String: Return the string itself
No Common Prefix: Return empty string
All Same Strings: Return the string
Empty Strings: Handle strings with length 0

Test Cases

def test_longestCommonPrefix():
    # Basic cases
    assert longestCommonPrefix(["flower","flow","flight"]) == "fl"
    assert longestCommonPrefix(["dog","racecar","car"]) == ""
    assert longestCommonPrefix(["interspecies","interstellar","interstate"]) == "inters"
    
    # Edge cases
    assert longestCommonPrefix([]) == ""
    assert longestCommonPrefix(["abc"]) == "abc"
    assert longestCommonPrefix(["",""]) == ""
    assert longestCommonPrefix(["abc","abc","abc"]) == "abc"
    assert longestCommonPrefix(["a","ab","abc"]) == "a"
    
    print("All tests passed!")

test_longestCommonPrefix()

Follow-up Questions

Case Insensitive: What if the comparison should be case-insensitive?
Unicode Support: How would you handle Unicode characters?
Longest Common Suffix: How would you find the longest common suffix?
Longest Common Substring: What if you need to find the longest common substring?
Performance with Large Arrays: How would you optimize for very large arrays?

Common Mistakes

Empty Array Handling: Not checking for empty input
Index Bounds: Not checking string length before accessing characters
Inefficient String Operations: Using expensive string operations
Early Termination: Not stopping when no common prefix exists
Single String Case: Not handling the case with only one string

Interview Tips

Start Simple: Begin with the most straightforward approach
Discuss Trade-offs: Compare vertical vs horizontal scanning
Handle Edge Cases: Always mention empty arrays and single strings
Optimize: Show how to optimize with early termination
Consider Alternatives: Mention divide and conquer approach