Longest Common Prefix

Problem Description

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"

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

Jump to Solution: Python Java C++ JavaScript C#

Python Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
            
        prefix = strs[0]
        for s in strs[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
                    
        return prefix

Java Solution

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        
        return prefix;
    }
}

C++ Solution

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (strs.empty()) {
            return "";
        }
        
        string prefix = strs[0];
        for (int i = 1; i < strs.size(); i++) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) {
                    return "";
                }
            }
        }
        
        return prefix;
    }
};

JavaScript Solution

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (!strs || strs.length === 0) {
        return "";
    }
    
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.slice(0, -1);
            if (!prefix) {
                return "";
            }
        }
    }
    
    return prefix;
};

C# Solution

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) {
            return "";
        }
        
        string prefix = strs[0];
        for (int i = 1; i < strs.Length; i++) {
            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) as we only use a constant amount of extra space

Solution Explanation

This solution uses a horizontal scanning approach:

We start with the first string as our initial prefix
For each remaining string:
- We repeatedly shorten the prefix until it's a prefix of the current string
- If the prefix becomes empty, we return an empty string

Key points:

We use string operations (startsWith, substring) to check and modify the prefix
We handle edge cases (empty array, empty strings) properly
The solution is efficient as we only need to scan each string once
We stop early if we find no common prefix