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

Constraints

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

Horizontal and Vertical Alignment Checking

You can find the common prefix by picking the first string as a reference and matching characters one by one against the remaining strings. At the first character mismatch, or when the reference string’s length exceeds any other string’s length, the current substring is the longest prefix. This vertical scanning approach ensures we stop immediately when a mismatch is found, saving execution cycles on long mismatches.

Solution 1: Vertical Scanning

Compare character-by-character from the beginning across all strings.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String first = strs[0];
        for (int i = 0; i < first.length(); i++) {
            char c = first.charAt(i);
            for (int j = 1; j < strs.length; j++) {
                // If we reach the end of any string or find a mismatch
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return first.substring(0, i);
                }
            }
        }
        return first;
    }
}

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""
        first = strs[0]
        for i in range(len(first)):
            char = first[i]
            for j in range(1, len(strs)):
                # Check bounds and matching characters
                if i == len(strs[j]) or strs[j][i] != char:
                    return first[:i]
        return first

#include <vector>
#include <string>

class Solution {
public:
    std::string longestCommonPrefix(std::vector<std::string>& strs) {
        if (strs.empty()) return "";
        std::string first = strs[0];
        for (int i = 0; i < first.length(); i++) {
            char c = first[i];
            for (size_t j = 1; j < strs.size(); j++) {
                if (i == strs[j].length() || strs[j][i] != c) {
                    return first.substr(0, i);
                }
            }
        }
        return first;
    }
};

Complexity Analysis

• Time Complexity: O(s) where s is the sum of all characters in all strings. In the worst case, we compare all characters of the strings.
• Space Complexity: O(1) auxiliary space as we only store the index variables.

Where It Breaks

If the array has an extremely long matching prefix but one string is empty, we must stop at index 0. The code correctly handles this since the inner loop’s check i == strs[j].length() triggers immediately at i = 0.

Common Mistakes

• Index out of bounds: Accessing strs[j].charAt(i) without checking if i is less than the length of strs[j].
• String reference errors: Forgetting to handle null arrays or empty array inputs.

Frequently Asked Questions

Can we sort the array first? Yes. Sorting the array lets you only compare the first and last strings, as they will have the maximum difference. Sorting takes O(n * k * log n) time, which is less optimal than standard vertical scanning if mismatches happen early.

What happens if the input has one string? The loops will skip the inner comparisons and return the single string itself.

← All Problems